动静布局

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

三要素

  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]赋予初值之后，就是写出状态转移方程