本文记录作者刷题过程中与动态规划题之背包相关的题目。

一、01背包问题

有N种具有体积和价值的物品，其中第i个物品的体积为weight[i]，价值为value[i]；每种物品都只有1个，放入一个容量为W的背包，问将哪些物品放入背包价值最大？

二维dp数组的写法

【状态定义】dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包的物品最大价值总和

【状态转移】按照是否放物品i来进行推导：

不放物品i：dp[i][j]=dp[i-1][j]

放物品i：dp[i][j]=dp[i-1][j-weight[i]]+value[i]

那么综合两种情况，取最大值：dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

【初始状态】

背包容量为0时，最大价值一定都为0：dp[i][0]=0

只放入物品i=0时：

当背包容量j<weight[0]时，最大价值dp[0][j]=0

当背包容量j>=weight[0]时，最大价值dp[0][j]=value[0]

相关代码：

// 背包容量为0时，最大价值一定都为0：dp[i][0]=0（可省略）
for (int j = 0 ; j < weight[0]; j++) dp[0][j] = 0;
// 只放入物品i=0时，当背包容量j>=weight[0]时，最大价值`dp[0][j]=value[0]`
for (int j = weight[0]; j <= bagWeight; j++) dp[0][j] = value[0];

相关模板：

vector<int> dp(weight.size(),vector<int>(bagWeight+1,0));//(物品种类数，背包最大容量数+1)
for(int j = weight[0]; j <= bagWeight; j++)dp[0][j] = value[0];
// 遍历物品的体积，即当前要添加物品的体积i
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    // 遍历背包容量，在当前背包容量为j时
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        // 如果新物品的体积比容量大，不可以添加，直接使用上一个值（剪枝）
        if (j < weight[i]) dp[i][j] = dp[i - 1][j]; 
        // 如果新物品的体积比容量小，可以添加，计算新的价值
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

一维dp数组的写法

对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来

对于一维dp，dp[j]都是通过本层即dp[j]覆盖计算而来

【状态定义】dp[j] 表示容量为j的背包，可以放入的物品最大价值总和

【状态转移】按照是否放物品i来进行推导：

不放物品i：dp[j]=dp[j]

放物品i：dp[j]=dp[j-weight[i]]+value[i]

那么综合两种情况，取最大值：dp[j]=max(dp[j],dp[j-weight[i]]+value[i])

【初始状态】

在取最大价值时，dp数组全部初始化为0即可

相关模板：

vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
// 一维数组的写法
vector<int> dp(weight.size(),vector<int>(bagWeight+1,0));//(物品种类数，背包最大容量数+1)
for(int j = weight[0]; j <= bagWeight; j++)dp[0][j] = value[0];
// 升序遍历物品的体积，即当前要添加物品的体积i
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    // 降序遍历背包容量，在当前背包容量为j时
    for(int j = bagweight; j >=weight[i] ; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

在上述写法中，背包容量的遍历顺序是从大到小，且必须先遍历物品后遍历背包，这是因为为了保证物品i只被放入一次背包。

假设物品i=0的体积很小但是价值很大：weight[0] = 1，价值value[0] = 15，dp[]

如果正序遍历：

dp[1] = max(dp[1], dp[1 - weight[0]] + value[0])=max(0,0+15)=15;//在容量为j=1的背包放入了，价值为15

dp[2] = max(dp[2], dp[2 - weight[0]] + value[0])=max(0,15+15)=30;//在容量为j=2的背包放入了2次，价值为30

如果倒序遍历：

dp[2] = max(dp[2], dp[2 - weight[0]] + value[0])=max(0,0+15)=15;//在容量为j=2的背包放入了，价值为15

dp[1] = max(dp[1], dp[1 - weight[0]] + value[0])=max(0,0+15)=15;//在容量为j=1的背包放入了，价值为15

剑指 Offer II 101. 分割等和子集（简单难度）

416. 分割等和子集（中等难度）

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

点评

nums的数组很大，用回溯法需要调优，很可能超时。

用动态规划法，将该问题看做一个01背包问题：

从重量为nums[i]和价值为nums[i]的一堆物品中挑选，放入容量为sum/2的背包中，问背包是否恰好装满？

/*01背包问题：本题可以理解为是否存在可以将一些重量和价值相等的物品放入容量为sum/2的背包中
    【状态定义】dp[j]表示容量为j的背包，可以放入的物品的最大总和
    【状态转移】假设放入重量为nums[i]，价值为nums[i]的物品，dp[j]放入nums[i]前的背包容量为dp[j-nums[i]]
    那么其价值为dp[j-nums[i]]+nums[i]，不放入该物品价值为dp[j]，放入该物品价值为dp[j-nums[i]]+nums[i]
    当前价值为dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
    【初始状态】dp[0]=0
    */
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(int n:nums)sum+=n;
        if(sum%2!=0) return false; // 如果数组和无法被2整除则肯定无法划分
        int target=sum/2;
        // dp[i]中的i表示背包内总和
        // 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
        // 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
        vector<int> dp(10001,0);
        // 升序遍历物品
        for(int i=0;i<nums.size();++i){
            // 倒序遍历背包
            for(int j=target;j>=nums[i];--j){
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        // 如果容量为target的背包的放入物品最大总和为target
        if (dp[target] == target) return true;
        return false;
    }

1049. 最后一块石头的重量 II（中等难度）

有一堆用整数数组 stones 表示的石头，其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块 石头。返回此石头最小的可能重量 。如果没有石头剩下，就返回 0。

点评

该题和1046. 最后一块石头的重量的区别是：该题要求任意挑选两块石头，返回剩下石头的最小重量；1046是每次挑选最重的两块石头，返回剩余石头的重量。显然该题已经不能使用优先级队列或者堆来解答。

一个官方证明的结论：任意选i块石头，使得他们的重量趋近于总重量的一半，这样和另一半抵消的差值就是最小的

所以该问题就可以转换为一个01背包问题：

在一堆重量和价值都为store[i]的物品中挑选，放入容量为sum/2的背包中，问背包最大可以容纳多少的物品

class Solution {
public:
    /* 
    一个官方证明的结论：任意选i块石头，使得他们的重量趋近于总重量的一半，这样和另一半抵消的差值就是最小的
    所以该问题就可以转换为一个01背包问题：
    在一堆重量和价值都为store[i]的物品中挑选，放入容量为sum/2的背包中，问背包最大可以容纳多少的物品
    */
    int lastStoneWeightII(vector<int>& stones) {
        int sum=0;
        for(int stone:stones) sum+=stone;
        int target=sum/2;
        // 定义：dp[j]表示容量为j的背包最大可以容纳的石头，j的最大重量为30*100/2+1
        vector<int> dp(15001,0);
        // 遍历物品
        for(int i=0;i<stones.size();++i){
            // 降序遍历背包
            for(int j=target;j>=stones[i];--j){
                dp[j]=max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        // 此时dp[target]就是所有石头中最趋近于总重量一半的重量，sum-dp[target]是另一半的重量
        return (sum-dp[target])-dp[target];
    }
};

474. 一和零（中等难度）

给定一个二进制字符串数组 strs 和两个整数 m 和 n 。返回 strs 的最大子集的长度，该子集中 最多有 m 个 0 和 n 个 1 。

点评

class Solution {
public:
    /*01背包问题：在重量为0的个数，价值为1的个数的一堆物品中，放入容量为m的价值为n的背包中
    该背包最多放入几个物品？
    【状态定义】dp[i][j]表示容量为i的、价值为j的背包的最大物品数为dp[i][j]
    【状态转换】dp[i][j]=dp[i-zeroNum][j - oneNum] + 1
    */
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
        // 升序遍历物品
        for (string str : strs) { 
            int oneNum = 0, zeroNum = 0;
            // 统计0和1的数字
            for (char c : str) {
                if (c == '0') zeroNum++;
                else oneNum++;
            }
            // 降序遍历背包
            for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

二、完全背包问题

一维数组的写法

有N种具有体积和价值的物品，其中第i个物品的体积为weight[i]，价值为value[i]；每种物品都有无数个，放入一个容量为W的背包，问将哪些物品放入背包价值最大？相关模板：

// 先遍历背包，再遍历物品
void test_CompletePack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;
    // 初始化dp数组
    vector<int> dp(bagWeight + 1, 0);
    // 升序遍历物品体积
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        // 升序遍历背包容量
        for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}

在完全背包中，遍历物品体积和遍历背包容量的先后顺序无所谓

排列数和组合数

vector<int> dp(target + 1, 0);
dp[0] = 1;
// 先遍历背包+后遍历物品，得到排列数
for (int j = 0; j <= target; j++) { 
    for (int num:nums) { 
        if (j - num >= 0 && dp[j] < INT_MAX - dp[j - num]) {
            dp[j] += dp[j - num];
        }
    }
}
// 先遍历物品+后遍历背包，得到组合数
for(int num:nums){
    for(int j=num;j<=target;j++){
        dp[j]+=dp[j-num];
    }
}
return dp[target];

322. 零钱兑换（中等难度）

给你一个整数数组 coins ，表示不同面额的硬币，可以认为每种硬币的数量是无限的；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

点评

假设有面值为 1, 2, 5 的硬币，原问题是求 amount 时的最少硬币数，

就是求 amount-1，amount-2，amount-5 的三个子问题中的最少硬币数，然后加一（再选一枚面值为 1, 2, 5 的硬币），这就是原问题的答案。

因为硬币数量没有限制，所以子问题之间没有相互制约，相互独立，即符合最优子问题。

class Solution {
public:
    /* 假设有面值为 1, 2, 5的硬币，原问题是求金额i时的最少硬币数，
    就是求 i-1，i-2，i-5 的三个子问题中的最少硬币数，
   然后加一（再选一枚面值为 1, 2, 5 的硬币）
    因为硬币数量没有限制，所以子问题之间没有相互制约，相互独立，即符合最优子问题。
    dp(i)=min(dp(i-1)+1,dp(i-2)+1,dp(i-5)+1)
    【定义dp】凑足总额为i的所需钱币最少个数为dp[i]
    【状态转移】凑足总额为i的所需钱币最少个数为dp[i]=min(dp[i],1+dp[i-coin[j]]),j负责遍历coin数组
    【初始条件】dp[0]=0，dp[-1]=-1，
    */
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount+1);//数组大小为amount+1，初始值为一个比该题目中答案都大的值
        dp[0] = 0;
        // 遍历所有的硬币的选择（物品）
        for (int coin:coins) { // 遍历物品
            // 遍历所有的amount（背包）
            for (int i = 0; i < amount+1; i++) { 
                // 如果子问题有解
                if (i- coin>=0) { 
                    dp[i] = min(dp[i],1+dp[i -coin]);
                }
            }
        }
        // 如果硬币没法凑出金额，那么dp[amount]为初始值
        if (dp[amount] == amount+1) return -1;
        return dp[amount];
    }
};

518. 零钱兑换 II（中等难度）

给你一个整数数组 coins ，表示不同面额的硬币，可以认为每种硬币的数量是无限的；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的硬币组合的个数 。如果没有任何一种硬币组合能组成总金额，返回 0。

输入：coins = [1, 2, 5], amount = 5
输出：4
解释：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

点评

转换为背包形式：有一个背包，最大容量为 amount，有一系列物品 coins，每个物品的重量为 coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？

这个问题和我们前面讲过的两个背包问题，有一个最大的区别就是，每个物品的数量是无限的，这也就是传说中的「完全背包问题」，没啥高大上的，无非就是状态转移方程有一点变化而已。

下面就以背包问题的描述形式，继续按照流程来分析。

class Solution {
public:
   /* 完全背包问题:向容量为amount的背包放入不同种类的体积和价值都为coins[i]的物品
   【状态定义】dp[j]表示可以凑出金额j的组合个数（不强调元素之间的顺序）
   【状态转移】在容量为j的背包里放第i个硬币coins[i]
       放第i个硬币的组合数：dp[j]=dp[j-coins[i]];// 容量为j的组合数和容量为j-coins[i]的组合数一样
       不放第i个硬币的组合数：dp[j]=dp[j]//使用(0,i-1)的结果
       综合来看共有dp[j]=dp[j]+dp[j-coins[i]];
    【初始状态】dp[0]=1
    【遍历顺序】先物品后背包
   */
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1,0);
        dp[0]=1;
        // 升序遍历所有物品
        for(int coin:coins){
            // 升序遍历所有背包容量
            for(int j=coin;j<=amount;j++){
                dp[j]+=dp[j-coin];
            }
        }
        return dp[amount];
    }
};

494. 目标和（中等难度）

给定一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个表达式 ，求共有几种表达式

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

点评

这题可以用回溯法，这里讲解动态规划法

原问题等同于： 找到nums一个正子集P和一个负子集N，使得总和等于target

假设nums = [1, 2, 3, 4, 5]，target = 3，一个可能的解决方案是+1-2+3-4+5 = 3

这里正子集P = [1, 3, 5]和负子集N = [2, 4]

那么sum(P) - sum(N) = target，sum(P) +sum(N) = sum(nums) ，可以得到：

sum(P) = （target + sum(nums)）/2，其中target + sum(nums)必须为偶数，否则不存在

该问题转换为：价值和重量都为nums[i]的物品中，放入容量为sum(P) 的背包中，问背包中的物品个数

 /*01背包问题：用价值与体积均为nums[i]的物品,恰好凑满容量为(target+sum)/2的背包方案数：装几件物品
    【状态定义】dp[j]为恰好能凑满容量为j的背包方案数
    【状态转移】背包容量能或者不能装下nums[i]：
        2.1 当不能装下nums[i]时,方案数直接继承之前的dp[j]
        2.2 当能装下nums[i]时,总的方案数为不考虑nums[i]的方案数+有nums[i]参与新增的方案数
            dp[j] += dp[j - nums[i]],dp[j - nums[i]]种方案与nums[i]共同凑成pos,即1*dp[j - nums[i]]
    【状态初始】装满容量为0的背包，有1种方法，就是装0件物品。
    */
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(int n:nums) sum+=n;
        if (abs(target) > sum) return 0; // 此时没有方案
        if((target+sum)%2!=0) return 0; // 此时没有方案
        int bagSize=(target+sum)/2;
        vector<int> dp(bagSize+1,0);
        dp[0]=1;
        // 升序遍历物品
        for(int i=0;i<nums.size();++i){
            // 降序遍历背包
            for(int j=bagSize;j>=nums[i];--j){
                dp[j]+=dp[j-nums[i]];
            }
        }
        return dp[bagSize];
    }

70. 爬楼梯（简单难度）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution {
public:
    /* 完全背包问题：容量为n的背包中放入体积为1或2的物品，问背包中放入物品的排列数
    */
    int climbStairs(int n) {
        vector<int> weights={1,2};
        vector<int> dp(n+1,0);
        dp[0]=1;
        for(int j=0;j<=n;++j){
            for(int weight:weights){
                if(j-weight>=0){
                    dp[j]=dp[j]+dp[j-weight];
                }
            }
        }
        return dp[n];
    }
};

377. 组合总和 Ⅳ（中等难度）

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。注意，数组nums中的每个数组可以使用多次，顺序不同的序列是做不同的组合。

输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 点评

/* 完全背包问题：向容量为target的背包中放入体积和价值都为nums[i]的物品
    问恰好放满背包的排列数量？
    【状态定义】dp[j]表示容量为j的背包恰好放满的数量
    【状态转移】dp[j]=dp[j]+dp[j-nums[i]]
    【初始状态】dp[0] = 1
    【遍历顺序】先背包后物品，注意dp[j] < INT_MAX - dp[j - num]
    */
int combinationSum4(vector<int>& nums, int target) {
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    // 升序遍历所有的背包容量
    for (int j = 0; j <= target; j++) { 
        // 升序遍历所有的物品体积
        for (int num:nums) { 
            if (j - num >= 0 && dp[j] < INT_MAX - dp[j - num]) {
                dp[j] =dp[j]+ dp[j - num];
            }
        }
    }
    return dp[target];
}

279. 完全平方数（中等难度）

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。完全平方数可以重复。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

class Solution {
public:
    /*完全背包问题： 向一个容积为n的背包中放入体积为完全平方数的物品，问背包中恰好放满时的物品的最少数量
    【状态定义】dp[j]表示容量为j的背包恰好放满的最少物品数量
    【状态转移】对于第i个物品：
    不放入：dp[j]=dp[j]
    放入：dp[j]=dp[j-weight[i]]+1
    综上：dp[j]=min(dp[j],1+dp[j-weight[i]])
    【初始状态】dp[0]=0
    */
    int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);// 取最小值，则初始值必须为最大值
        dp[0]=0;
        // 遍历物品
        for(int i=1;i*i<=n;i++){
            int weight=i*i;
            // 遍历背包容量
            for(int j=1;j<=n;j++){
                if(j-weight>=0){
                    dp[j]=min(dp[j],1+dp[j-weight]);
                }
            }
        }
        return dp[n];
    }
};

139. 单词拆分（中等难度）

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

class Solution {
public:
    /* 完全背包问题：容量为s的背包中放入体积为wordDict的物品
    【状态定义】dp[j]表示s的长度为i时，可以拆分字典中的单词为j的背包是否可以恰好放入物品
    【状态转移】对于物品wordDict[i]
    如果原来的dp[j] 是true，且 [i, j] 这个区间的子串出现在字典里，那么dp[j]一定是true。（i < j ）。
    【初始状态】dp[0]=true
    */
    bool wordBreak(string s, vector<string>& wordDict) {
        // 将单词字典存入哈希集合
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        // 动态数组
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        // 遍历所有的物品
        for (int i = 0; i < s.size(); i ++){ 
            // 遍历所有的字符串的长度
            for (int j = i; j <= s.size(); j++){       // 遍历物品
                string word = s.substr(i, j - i); //substr(起始位置，截取的个数)
                // 如果单词字典中存在该单词并且上一个区间也是true
                if (wordSet.count(word)&& dp[i]) {
                    dp[j] = true;
                }
            }
        }
        return dp[s.size()];
    }
};