参考：一套框架解决「背包问题」

背包问题的特征：给定一个 target（可能需要间接求出）和一个 nums 数组，问：能否通过 nums 数组中各元素的各种排列组合得到 target？

1、01 背包问题

原问题： 给定 n 件物品，物品的重量为 w[i]，物品的价值为 c[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

01 背包问题的特征：**nums** 数组中元素都不能重复选取

解法：外循环遍历 **nums** 数组，内循环倒序遍历 **target**

  • 注意 01 背包问题的内循环是倒序的，因为 01 背包问题的原始解法是使用二维 dp 数组，对于简化到一维后的 dp 数组， 假设当前外循环遍历的元素为 val，内循环遍历到 j，dp[j] 参考的实际上应该是上一行的 dp[j - val]，那么如果内循环正序遍历，状态 dp[j - val] 就已经被更新了，不再是上一行的状态了

例 1：分割等和子集

[中等] 416. 分割等和子集

  1. class Solution {
  2. public:
  3.     bool canPartition(vector<int>& nums) {
  4.         int len = nums.size();
  5.         // 先对数组中所有元素求和
  6.         int sum = 0;
  7.         for(int i = 0; i < len; ++i)
  8.             sum += nums[i];
  9.         // 如果和为奇数，直接返回 false，不可能分为两个和相同的子集
  10.         if(sum % 2 == 1)
  11.             return false;
  12.         // 将和的一半作为 01背包问题的 target
  13.         int target = sum / 2;
  15.         // 动态规划数组，dp[i] 代表是否存在和为 i 的组合
  16.         vector<bool> dp(target + 1, false);
  17.         dp[0] = true;    // 初始化，存在和为 0 的组合
  18.         // 状态转移
  19.         for(int i = 0; i < len; ++i)            // 外层循环遍历数组中的每个元素值 nums[i]
  20.         {
  21.             int val = nums[i];
  22.             // 内层循环之所以倒序，因为dp数组是从二维优化为一维的
  23.             // dp[j] 实际上本来是和上一行的 dp[j-val] 有关
  24.             // 如果正序遍历 target，那么 dp[j-val] 已经是更新过的状态，而不再是上一行的 dp 值
  25.             for(int j = target; j >= val; --j)    // 内层循环倒序遍历 target 的值
  26.                 dp[j] = dp[j] || dp[j - val];
  27.         }
  28.         return dp[target];
  29.     }
  30. };

例 2：目标和

[中等] 494. 目标和

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int len = nums.size();
        // 求数组中所有元素的和
        int sum = 0;
        for(int i = 0; i < len; ++i)
            sum += nums[i];
        // 特例：直接返回 false
        if(target > sum || (target + sum) % 2 == 1)
            return false;

        // 设X代表数组中最终代表正数的元素的和
        // 设Y代表数组中最终代表负数的元素的和
        // 则X+Y=sum，X-Y=target，因此有 X=sum+target/2
        // 这个X就是01背包问题的目标值
        int posTarget = (target + sum) / 2;
        vector<int> dp(posTarget + 1, 0);
        dp[0] = 1;
        for(int i = 0; i < len; ++i)                // 外层循环遍历nums数组
        {
            int val = nums[i];
            for(int j = posTarget; j >= val; --j)    // 内层循环倒序遍历 target
                dp[j] += dp[j - val];
        }
        return dp[posTarget];
    }
};

2、完全背包问题

完全背包问题与 01 背包问题的区别：**nums** 数组中元素可以重复选取

2.1 组合问题

组合问题：求组合数（[1, 2, 1] 和 [1, 1, 2] 是同一种组合，是不同的排列）
解法：外层循环遍历 **nums** 数组，内层循环（正序）遍历 **target**

例 1：零钱兑换 II

[中等] 518. 零钱兑换 II

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for(int i = 0; i < coins.size(); ++i)
        {
            for(int j = coins[i]; j <= amount; ++j)
                dp[j] += dp[j - coins[i]];
        }
        return dp[amount];
    }
};

2.2 排列问题

排列问题：求排列数（[1, 2, 1] 和 [1, 1, 2] 是不同的排列）
解法：外层循环遍历 **target**，内层循环（正序）遍历 **nums** 数组

例 1：组合总和 IV

[中等] 377. 组合总和 Ⅳ

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // 动态规划 dp 数组，dp[i] 代表和 i 的排列数
        vector<int> dp(target + 1, 0);
        dp[0] = 1;    // 初始化
        for(int i = 0; i <= target; ++i)            // 外层循环 target
        {
            for(int j = 0; j < nums.size(); ++j)    // 内层循环 nums 数组的元素
            {
                if(i - nums[j] >= 0 && dp[i - nums[j]] < INT_MAX - dp[i])
                    dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
};

进阶：此题求的是排列数量，如果要求输出所有的组合呢？需要使用递归回溯，参见：
[中等] 39. 组合总和

2.3 最少数量

问题：求使得达到 target 所选取的 nums 数组的元素的数量最少，求这个最少数量
解法：归为排列问题和组合问题都可以

  • 由于排列问题的做法更符合动态规划的直觉，因此我使用的是排列问题的做法：外层循环遍历 target，内层循环遍历 nums 数组

例1：零钱兑换

[中等] 322. 零钱兑换

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for(int i = 1; i <= amount; ++i)
        {
            for(int j = 0; j < coins.size(); ++j)
            {
                if(i - coins[j] >= 0 && dp[i - coins[j]] != INT_MAX && dp[i - coins[j]] + 1 < dp[i])
                    dp[i] = dp[i - coins[j]] + 1;
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

例 2：完全平方数

[中等] 279. 完全平方数

class Solution {
public:
    int numSquares(int n) {
        // dp 数组，dp[i] 代表和为 n 的完全平方数的最少数量 
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;    // 初始化
        for(int i = 1; i <= n; ++i)            // 外层循环 target
        {
            for(int j = 1; j * j <= i; ++j)    // 内存循环平方数
                dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
        return dp[n];
    }
};