一、动归五部曲

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

    二、题目实战

    2.1 基础题目

    509. 斐波那契数
    70. 爬楼梯
    746. 使用最小花费爬楼梯

    这三道题目作为动归入门题目，主要是熟悉动归五部曲以及方法论

  1. class Solution {
  2. public:
  3.     int minCostClimbingStairs(vector<int>& cost) {
  4.         int len = cost.size();
  5.         vector<int> dp(len, 0);
  6.         dp[0] = cost[0];
  7.         dp[1] = cost[1];
  9.         for (int i = 2; i < len; i++) {
  10.             dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
  11.         }
  13.         return min(dp[len - 1], dp[len - 2]);
  14.     }
  15. };
  17. // 这道题目其实主要是题意不太好理解，仔细理解题意，本身不难

2.2 路径题目

62. 不同路径

  1. // 这道题是基础的二维dp数组题目，当然可以简化为一维的dp数组
  2. // 二维的dp数组，注意第一行和第一列的初始化
  3. // 递推公式如下：
  4. dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

63. 不同路径 II

  1. // 将有障碍物的地方赋值为0。在初始化的时候要注意：障碍物之后都应该赋值0。
  2. if (obstacleGrid[i][j] == 1) dp[i][j] = 0;
  3. else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

2.3 343. 整数拆分

这道题目最难的地方在于递推公式：dp[i]取三者的最大值（dp[i]，dp[i - j] j，(i - j) j）
可以理解为：j (i - j) 是单纯的把整数拆分为两个数相乘，而j dp[i - j]是拆分成两个以及两个以上的个数相乘。

  1. for (int i = 3; i <= n ; i++) {
  2.     for (int j = 1; j < i - 1; j++) {
  3.         dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
  4.     }
  5. }

2.4 96. 不同的二叉搜索树

这道题目还是很难的，递归公式需要找规律，很难。
dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

  1. for (int i = 1; i <= n; i++) {
  2.     for (int j = 1; j <= i; j++) {
  3.         dp[i] += dp[j - 1] * dp[i - j];
  4.     }
  5. }

2.5 0-1背包问题

416. 分割等和子集
将问题转化为0-1背包问题：

  • 背包的体积为sum / 2
  • 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
  • 背包如果正好装满，说明找到了总和为 sum / 2 的子集。

  • 背包中每一个元素是不可重复放入。

    1. class Solution {
    2. public:
    3.   bool canPartition(vector<int>& nums) {
    4.       int sum = 0;
    5.       for (int i : nums) {
    6.           sum += i;
    7.       }
    8.       if (sum % 2 != 0) return false;
    10.       int target = sum / 2;
    11.       vector<int> dp(target + 1, 0);
    12.       for (int i = 0; i < nums.size(); i++) {
    13.           for (int j = target; j >= nums[i]; j--) {
    14.               dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    15.           }
    16.       }
    18.       return dp[target] == target ? true : false;
    19.   }
    20. };

1049. 最后一块石头的重量 II
这道题跟上一道几乎一样，唯一不同在于最后的答案求解

  1. int ans = sum - 2 * dp[target];

494. 目标和

重点题目！ 这道题虽然也是0-1背包问题，但是求解的是”方式数目“。递推公式需要做出改变。

对问题进行转化：

  1. left组合 - right组合 = target
  2. left + right = sum

  3. left = (target + sum) / 2

    1. class Solution {
    2. public:
    3.  int findTargetSumWays(vector<int>& nums, int target) {
    4.      int sum = 0;
    5.      for (auto i : nums) {
    6.          sum += i;
    7.      }
    9.      // 两种特殊情况，要额外进行考虑
    10.      // 尤其是第一个，测试用例中专门考察了
    11.      if (abs(target) > sum) return 0;
    12.      if ((target + sum) % 2 != 0) return 0;
    14.      int bag = (target + sum) / 2;
    15.      vector<int> dp(bag + 1, 0);
    16.      dp[0] = 1; // 为0的时候方案初始化为一种
    18.      for (int i = 0; i < nums.size(); i++) {
    19.          for (int j = bag; j >= nums[i]; j--) {
    20.              // 要求方案的数目，递推公式一般都是类似这种形式
    21.              dp[j] += dp[j - nums[i]];
    22.          }
    23.      }
    25.      return dp[bag];
    26.  }
    27. };

474. 一和零

二维0-1背包问题，即背包有两个

  1. class Solution {
  2. public:
  3.     int findMaxForm(vector<string>& strs, int m, int n) {
  4.         // 二维0-1背包
  5.         // 如果设置为（m, n）的大小，则必须对dp[0][0]初始化；为了避免这一麻烦的步骤，因此设置为
  6.         vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
  8.         // 先遍历物品
  9.         for (int k = 0; k < strs.size(); k++) {
  10.             int numZero = 0, numOne = 0;
  11.             for (auto c : strs[k]) {
  12.                 if (c == '0') numZero++;
  13.                 else numOne++;
  14.             }
  16.             // 倒向遍历背包1
  17.             for (int i = m; i >= numZero; i--) {
  18.                 // 倒向遍历背包2
  19.                 for (int j = n; j >= numOne; j--) {
  20.                     // 当子串c能够放进去的时候，最大子集的长度 + 1
  21.                     dp[i][j] = max(dp[i][j], dp[i - numZero][j - numOne] + 1);
  22.                 }
  23.             }
  24.         }
  26.         return dp[m][n];
  27.     }
  28. };

2.6 完全背包问题

完全背包问题，物品和背包的问题都是正向遍历// 对于纯完全背包问题，物品和背包的遍历顺序是可以颠倒的

但是在求装满背包有几种方案的时候，遍历顺序非常关键 如果求组合数就是外层for循环遍历物品，内层for遍历背包。 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

组合不强调元素之间的顺序，排列强调元素之间的顺序。

518. 零钱兑换 II

  1. // 这道题求 完全背包问题的组合数
  2. // 先遍历物品，再遍历背包
  3. int change(int amount, vector<int>& coins) {
  4.         vector<int> dp(amount + 1, 0);
  5.         // dp[0]一定要初始化
  6.         dp[0] = 1;
  8.         for (int i = 0; i < coins.size(); i++) {
  9.             for (int j = coins[i]; j <= amount; j++) {
  10.                 // 求几种方案的递推公式
  11.                 dp[j] += dp[j - coins[i]];
  12.             }
  13.         }
  15.         return dp[amount];
  16.     }

377. 组合总和 Ⅳ

  1. // 完全背包问题的排列数
  2. int combinationSum4(vector<int>& nums, int target) {
  3.         // 根据示例可知，本题实际上是求解排列个数
  4.         vector<int> dp(target + 1, 0);
  5.         dp[0] = 1;
  7.         // 先遍历背包，再遍历物品
  8.         for (int i = 1; i <= target; i++) {
  9.             for (int j = 0; j < nums.size(); j++) {
  10.                 // 确保i >= nums[j]
  11.                 // 这道题目中有个测试用例超出了INT_32的范围
  12.                 if (i >= nums[j] && dp[i] < INT_MAX - dp[i - nums[j]]) {
  13.                     dp[i] += dp[i - nums[j]];
  14.                 }
  15.             }
  16.         } 
  18.         return dp[target];
  19.     }

322. 零钱兑换

这道题求 最少的硬币个数，属于完全背包的组合问题。

  1. // 难点在于递推公式和初始化
  2. int coinChange(vector<int>& coins, int amount) {
  3.     // 递推公式为 min()，所以需要初始化为int型最大值
  4.     vector<int> dp(amount + 1, INT32_MAX);
  5.     // dp[0]必须初始化为0，根据递推公式得来
  6.     dp[0] = 0;
  8.     for (int i = 0; i < coins.size(); i++) {
  9.         for (int j = coins[i]; j <= amount; j++) {
  10.             // 判断此种情况下没必要更新，并且避免dp[j - coins[i]] + 1超出int范围
  11.             if (dp[j - coins[i]] != INT32_MAX) {
  12.                 // 如果硬币能够放进去，则数目 + 1
  13.                 dp[j] = min(dp[j], dp[j - coins[i]] + 1);
  14.             }
  15.         }
  16.     }
  18.     return dp[amount] == INT32_MAX ? -1 : dp[amount];
  19. }