基本技巧

动态规划是指这样一类题目：

  • 可通过穷举的办法解决
  • 存在重叠子问题
  • 具备最优子结构
  • 需要明确的状态转移方程

动态规划解题流程无外乎：

  1. 确定状态
  2. 定义dp函数/数组含义
  3. 明确选择
  4. 明确base case

参照算法刷题思路小节笔记，因为动态规划的上述特性，决定了动态规划算法存在进步与优化的空间。 用最简单的斐波那契数列来看，暴力的方法是递归所有子问题，但因为存在重叠情况，所以采用了备忘录、自底向上等方法来优化。
熟练掌握解题流程，然后通过优化方式来带入思考，能够在时间空间上都有一定进步。

什么是最优子结构

量化子结构是动态规划的必要条件，目的是为了求解最值。 动态规划即根据base case往后推导，不断找到最优子结构，一定要证明状态转移方程。

dp数组的方向

观察可发现，在动态规划设计中各种遍历方式都有，但是一定要满足如下两点：

  1. 遍历的过程中，所需的状态必须是已经计算出来的。
  2. 遍历的终点必须是存储结果的那个位置。

简单来说就是新结果必须基于已有结果，要么递归再运算，要么自底向上。无论哪种方向，终点必须是求解结果。

base case 和 备忘录初始值

这一篇说实话，写的不好，不建议参考，可以根据给出的习题，自己思考解决。 只要认真执行动态规划四步走，在明确了状态选择时，先写出代码再逐步优化即可。

状态压缩技巧

状态压缩的核心，就是将二维数组压缩到一维数组即可。 如果之前阅读了基础知识相关部分，可以把这一篇和打家劫舍里的内容结合起来看，如下图。 打家劫舍中存在下一状态仅仅与上一状态两种取值有关，所以无需保存过程值，仅计算结束值即可。

WIP：动态规划篇 - 图1

需要注意，在求解动态规划的过程中，忌讳一上来就写的贼漂亮，当然这样很好，但是程序的可阅读性差，思考复杂度高，并不适合新手操作。
明确动态规划的本质还是可以穷举解决的问题，再通过解决重复子问题（备忘录or自底向上），状态压缩进而空间压缩，逐步优化。 【完成比完美重要】逐步思考而后再运用娴熟。

回溯算法与动态规划

这里采用了leetcode-494题，很好的比较了回溯算法与动态规划的差异性。 简单来说，回溯算法简单清晰，但是算法时间复杂度高，即使经过剪枝的情况下，仍然没有很大改进。

但是动态规划则不一样，通过划分子问题，再加之改造，容易得到非常魔性的解法…而且还会和初始思路偏差较大。 但是不用慌张，这里的动态规划套路是优先的，只要通过多刷题肯定能掌握。小熊肯定没问题√

WIP：动态规划篇 - 图2

  1. class Leetcode494 {
  3.     int res = 0;
  5.     /**
  6.      * 第一种写法，回溯实现
  7.      * @param nums
  8.      * @param target
  9.      * @return
  10.      */
  11.     public int findTargetSumWays(int[] nums, int target) {
  12.         backtrack(nums, 0, 0, target);
  13.         return res;
  14.     }
  16.     void backtrack(int[] nums, int sum, int i, int target) {
  17.         if (i == nums.length && sum == target) {
  18.             res += 1;
  19.         }
  20.         if (i == nums.length) {
  21.             return;
  22.         }
  23.         backtrack(nums, sum + nums[i], i + 1, target);
  24.         backtrack(nums, sum - nums[i], i + 1, target);
  25.     }
  27.     /**
  28.      * 第二种写法，回溯实现，针对函数传参优化
  29.      * @param nums
  30.      * @param target
  31.      * @return
  32.      */
  33.     public int findTargetSumWays(int[] nums, int target) {
  34.         backtrack(nums, 0, target);
  35.         return res;
  36.     }
  38.     void backtrack(int[] nums, int i, int rest) {
  39.         if (i == nums.length) {
  40.             if (rest == 0) {
  41.                 res += 1;
  42.             }
  43.             return;
  44.         }
  45.         backtrack(nums, i + 1, rest + nums[i]);
  46.         backtrack(nums, i + 1, rest - nums[i]);
  47.     }
  49.     /**
  50.      * 【消除重叠子问题】
  51.      * 第三种写法，回溯剪枝
  52.      * @param nums
  53.      * @param target
  54.      * @return
  55.      */
  56.     public int findTargetSumWays(int[] nums, int target) {
  57.         return backtrack(nums, 0, target);
  58.     }
  60.     Map<String, Integer> memo = new HashMap<>();
  62.     int backtrack(int[] nums, int i, int rest) {
  63.         if (i == nums.length) {
  64.             if (rest == 0) {
  65.                 return 1;
  66.             }
  67.             return 0;
  68.         }
  69.         if (memo.contains("" + (i + 1) + rest)) {
  70.             return memo.get("" + (i + 1) + rest);
  71.         }
  73.         memo.put("" + (i + 1) + rest, backtrack(nums, i + 1, rest + nums[i]) + backtrack(nums, i + 1, rest - nums[i]));
  74.         return memo.get("" + (i + 1) + rest);
  75.     }
  77.     /**
  78.      * 【动态规划解法】
  79.      *
  80.      * @param nums
  81.      * @param target
  82.      * @return
  83.      */
  84.     public int findTargetSumWays(int[] nums, int target) {
  85.         int sum = 0;
  86.         for (int n : nums) {
  87.             sum += n;
  88.         }
  89.         if (sum < target || (sum + target) % 2 == 1) {
  90.             return 0;
  91.         }
  92.         return subsets(nums, (sum + target) / 2);
  93.     }
  95.     int subsets(int[] nums, int sum) {
  97.     }
  98. }

动态规划解法推导过程如下：

  1. 该问题计算的是所有数字经过分配运算符，运算后是否等于给定值
  2. 那么问题其实是可以划分子集计算，我们将nums划分为两个子集A、B，分别代表分配+、-，那么可以得到如下运算关系： sum(A) - sum(B) = target sum(A) = target + sum(B)
    sum(A) + sum(A) = target + sum(B) + sum(A)
    2 * sum(A) = target + sum(nums)
    sum(A) = (target + sum(nums)) / 2
  3. 得到了上面的函数，就可以转而定义出计算子集函数 int subsets(int[] nums, int sum){} 问题转而变成了背包问题的标准形式

子序列类型问题

背包类型问题

贪心类型问题

应用题型