关于java:算法入门之动态规划

动静布局

动静布局个别用于求最值问题，外围原理就是穷举，把所有答案算进去，求个最值不是轻轻松松吗？不过动静布局比穷举好的中央在于，动静布局存储了计算出来的值，再后续解决重叠子问题时，间接从内存获取。这就要求了动静布局解决的问题必须要有最优子结构，这样以后问题的值就能够通过子问题的最优解计算失去。

三要素

1. 重叠子问题
2. 最优子结构
3. 状态转移方程

思路

1. 间接创立一个数组存储子问题答案 dp[]
2. 了解题意，写出状态转移方程dp[i] 和 dp[i-1]之间的关系
3. 用代码写出状态转移方程即可

实际

题目一

leetcode338：比特位计数

思维过程

设dp[]为一个存储后果的数组汇合，当传入一个整数i时，能够失去二进制数1的个数为dp[i]。
如何书写状态转移方程？dp[i]和dp[i-1]之间存在什么关系？
带入二进制思考，整数i的二进数1的个数等于去除了二进制最高位的整数x的1的个数加1。
举例：101的1的个数等于01的1的个数+1 -> dp[i] = dp[x] + 1 -> i = x + i的最高位的值

代码

 public static int[] countBits(int n) {
        int[] dp = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            dp[i] = dp[i - highBit] + 1;
        }
        return dp;
    }

代码解析

1. 定义dp数组
2. 定义hightBit为最高位的值，通过i & (i – 1)位运算计算
3. 写dp[i] = dp[i – highBit] + 1状态转移方程

题目二

剑指 Offer 42：间断子数组的最大和

思维过程

设dp[]为一个存储后果的数组汇合，当传入一个整数i时，能够失去数组前i个值的最大和为dp[i]。
如何书写状态转移方程？dp[i]和dp[i-1]之间存在什么关系？
带入题目思考，题目要求是间断，所以dp[i]必然蕴含数组nums[i]的值，dp[i-1]为正数时，对于dp[i]是个累赘，间接舍弃，如果dp[i-1]为负数，那么最大值为dp[i-1] + nums[i]。
所以状态转移方程为：
当dp[i-1]<0,dp[i] = nums[i]
当dp[i-1]>=0,dp[i] = dp[i-1] + nums[i]

代码

public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                max = nums[i];
                dp[i] = nums[i];
            } else {
                if (dp[i - 1] < 0) {
                    dp[i] = nums[i];
                } else {
                    dp[i] = dp[i - 1] + nums[i];
                }
                if (dp[i] > max) {
                    max = dp[i];
                }
            }
        }
        return max;
    }

代码解析

1. 定义dp数组
2. 定义max保留最优解
3. for循环给dp[0]赋予初值之后，就是写出状态转移方程