https://en.wikipedia.org/wiki/Dynamic_programming
动态规划，dynamic programming也就是动态递推。
simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner。
动态规划和递归与分治没有本质的区别，关键是看有无最优子结构。
共性：找重复子问题
差异：最优子结构， 中途可以淘汰次优解。

动态规划的关键点

  • 最优子结构 **opt[n] = bestof(opt[n-1], opt[n-2],...)**，也就是子问题

最优子结构就是推导出的第N步的值，是前面几个值的最佳值，这个最佳值有时候就是简单的累加，像63.不同路径
有些时候是取最大值，或最小值。

  • 存储中间状态 **opt[i]**
  • 递推公式，美其名曰状态转移方程，DP方程

二维路径：opt[i,j]= opt[i-1][j] + opt[i][j-1]
处理动态规划的问题，要养成以上三步走的习惯。

什么样的题目想到动态规划

  • 看题目的问法，只问最优值是多少，没有要我们求最优解，一般情况下就是「动态规划」可以解决的问题；
  • 求多少种方案的问题。

将空间复杂度降为一维

  • 当 当前的状态只需要前一个状态时，则可以通过一个变量，递推该变量求得结果

    1. 53.题最大子序和
    2. dp[0] = nums[0];
    3. int maxNums = dp[0];
    4. for (int i = 1; i < len; i++) {
    5.   dp[i] = max(dp[i-1], 0) + nums[i];
    6.   if (dp[i] > maxNums) {
    7.       maxNums = dp[i];
    8.   }
    9. }
    10. --优化:
    11. int m = nums[0];
    12. int maxNums = m;
    13. for (int i = 1; i < len; i++) {
    14.   m = max(m, 0) + nums[i];
    15.   if (m > maxNums) 
    16.   maxNums = m;
    17. }

  • 当 当前状态需要前两个状态时， 则可以通到两个变量，递推这两个变量得到结果

定义变量时，从最后一个位置开始定义，下次循环时，依次往前递推一个位置即可。

  1. 198.打家劫舍
  2. dp[0] = nums[0];
  3. dp[1] = max(nums[0], nums[1]);
  4. for (int i = 2; i < len; i++) {
  5.     dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
  6. }
  8. --优化 
  9. --相当于从后往前推 i-2 = a; i-1 = b; i=c; 最后一个是a，则下一轮循环时就是将a往前移动位置即 a = b;同理，b = c;
  11. int a = 0， b = 0;
  12. for (int i = 0; i < len; i++) {
  13.     int c = max(b, a + nums[i]);
  14.     a = b;
  15.     b = c;
  16. }