动态规划 – 背包问题

背包问题是动态规划的经典问题，背包问题可以分为0/1背包，完全背包，多重背包等。

0/1背包：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

完全背包：基础定义和0/1背包基本一致，区别在于每件物品可以重复拿无穷次。

多重背包：基础定义和0/1背包完全一致，区别在于每件物品最多可以拿time[i]次。

之前我们讲到过，递归+记忆化搜索 -> 动态递归 -> 空间压缩，所以在讲解背包问题时，我们也会给出递归解法，递归+记忆化搜索解法，动态规划解法，空间压缩四种解法。

1 0/1背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

总的来讲，0/1背包就是选或者不选问题的代表。

f(i, w)定义为选择到第i件物品时，背包剩余容量为w的背包最大价值。

f(i, w) = max(f(i-1, w), f(i-1, w-weight[i])+value[i])

不选择物品i                选择物品i

1.1 模版

• 至多装capacity，求方案数/最大价值和
• 恰好装capacity，求方案数/最大/最小价值和
• 至少装capacity，求方案数/最小价值和

公式变形：

• 1 求方案数：f(i, w) = f(i-1, w)+f(i-1, w-weight[i])+value[i]
• 2 求最大价值和：f(i, w) = max(f(i-1, w), f(i-1, w-weight[i])+value[i])
• 3 求最小价值和：f(i, w) = min(f(i-1, w), f(i, w-weight[i])+value[i])

模版：

void xx(vector& weight, vector& value, int bagweight) {
    // 1 定义dp数组
    vector<vector> dp(weight.size(), vector(bagweight + 1, 0));

    // 2 初始化dp数组
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

    // 3 迭代
    // weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        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]);

        }
    }
    cout << dp[weight.size() - 1][bagweight] << endl;
}

1.2 真题：目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

题目分析：

该题目可以转化为0/1背包问题，假设添加+的数的和为p，添加-的数的和为q，全体数的和为s，则p+q=s，同时p-q=target，故p=(s+target)/2，问题变成从nums数组中选择一些数字的和为p。

1.2.1 暴力递归

利用递归中的参数作为入口的检测：

• 1 选取的数字溢出数组nums
• 2 选取的数字比target还大，则不选择该数字

class Solution {
public:
    int dfs(int i, int target, vector& nums){
        if (i < 0){
            if (target == 0) return 1;
            else return 0;
        }
        if (target < nums[i]) return dfs(i-1, target, nums);
        return dfs(i-1, target, nums) + dfs(i-1, target-nums[i], nums);
    }

    int findTargetSumWays(vector& nums, int target) {
        int m = nums.size();
        int total = 0;
        for(auto num:nums) total+=num;
        target += total;
        if (target < 0 && target%2 == 1) return 0;
        target /= 2;
        return dfs(m-1, target, nums);
    }
};

1.2.2 记忆化搜索

class Solution {
public:
    int dfs(int i, int target, vector& nums, vector<vector>& dp){
        if (i < 0){
            if (target == 0) return 1;
            else return 0;
        }
        if (target < nums[i]) return dfs(i-1, target, nums, dp);
        if (dp[i][target] != -1) return dp[i][target];
        dp[i][target] =  dfs(i-1, target, nums, dp) + dfs(i-1, target-nums[i], nums, dp);
        return dp[i][target];
    }

    int findTargetSumWays(vector& nums, int target) {
        int m = nums.size();
        int total = 0;
        for(auto num:nums) total+=num;
        target += total;
        if (target < 0 || target%2 == 1) return 0;
        target /= 2;
        vector<vector> dp(m, vector(target+1, -1));
        int result = dfs(m-1, target, nums, dp);
        return result;
    }
};

1.2.3 动态规划

class Solution {
public:
    int findTargetSumWays(vector& nums, int target) {
        int m = nums.size();
        int total = 0;
        for(auto num:nums) total+=num;
        target += total;
        if (target < 0 || target%2 == 1) return 0;
        target /= 2;
        vector<vector> dp(m+1, vector(target+1));
        dp[0][0] = 1;
        for(int i=0; i< m; i++){
            for(int j=0; j <= target; j++){
                if (j < nums[i]) dp[i+1][j] = dp[i][j];
                else dp[i+1][j] = dp[i][j] + dp[i][j-nums[i]];
            }
        }
        return dp[m][target];
    }
};

1.2.4 空间压缩

这里我们观察到递推公式中的第一个索引总是i+1和i.

这告诉我们其实第一个索引只需要2个变量即可。故将i变成i%2，i+1变成(i+1)%2.

class Solution {
public:
    int findTargetSumWays(vector& nums, int target) {
        int m = nums.size();
        int total = 0;
        for(auto num:nums) total+=num;
        target += total;
        if (target < 0 || target%2 == 1) return 0;
        target /= 2;
        vector<vector> dp(2, vector(target+1));
        dp[0][0] = 1;
        for(int i=0; i< m; i++){
            for(int j=0; j <= target; j++){
                if (j < nums[i]) dp[(i+1)%2][j] = dp[i%2][j];
                else dp[(i+1)%2][j] = dp[i%2][j] + dp[i%2][j-nums[i]];
            }
        }
        return dp[m%2][target];
    }
};

2 完全背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品可以使用任意次，求解将哪些物品装入背包里物品价值总和最大。

f(i, w)定义为选择到第i件物品时，背包剩余容量为w的背包最大价值。

f(i, w) = max(f(i-1, w), f(i, w-weight[i])+value[i])

不选择物品i              选择物品i

2.1 模版

void xx(vector& weight, vector& value, int bagweight) {
    // 1 定义dp数组
    vector<vector> dp(weight.size(), vector(bagweight + 1, 0));

    // 2 初始化dp数组
    for (int j = weight[0]; j <= bagweight; j++) {
        dp[0][j] = value[0];
    }

    // 3 迭代
    // weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        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][j - weight[i]] + value[i]);

        }
    }
    cout << dp[weight.size() - 1][bagweight] << endl;
}

2.2 真题：零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

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

2.2.1 暴力递归

class Solution {
public:
    int dfs(int i, int amount, vector& coins){
            if (i < 0){ if (amount == 0) return 0; else return INT_MAX/2; } if (coins[i] > amount) return dfs(i-1, amount, coins);
            return min(dfs(i-1, amount, coins), dfs(i, amount-coins[i], coins)+1);
        }
        
    int coinChange(vector& coins, int amount) {
        int n = coins.size();
        int result = dfs(n-1, amount, coins);
        return result >= INT_MAX/2?-1:result;
    }
};

2.2.2 记忆化搜索

class Solution {
public:
    int dfs(int i, int amount, vector& coins, vector<vector>& dp){
            if (i < 0){ if (amount == 0) return 0; else return INT_MAX/2; } if (coins[i] > amount) return dfs(i-1, amount, coins, dp);
            if (dp[i][amount] != -1) return dp[i][amount];
            dp[i][amount] = min(dfs(i-1, amount, coins, dp), dfs(i, amount-coins[i], coins, dp)+1);
            return dp[i][amount];
        }
        
    int coinChange(vector& coins, int amount) {
        int n = coins.size();
        vector<vector> dp(n, vector(amount+1, -1));
        int result = dfs(n-1, amount, coins, dp);
        return result >= INT_MAX/2?-1:result;
    }
};

2.2.3 动态规划

class Solution {
public:
    int dfs(int i, int amount, vector& coins, vector<vector>& dp){
            if (i < 0){ if (amount == 0) return 0; else return INT_MAX/2; } if (coins[i] > amount) return dfs(i-1, amount, coins, dp);
            if (dp[i][amount] != -1) return dp[i][amount];
            dp[i][amount] = min(dfs(i-1, amount, coins, dp), dfs(i, amount-coins[i], coins, dp)+1);
            return dp[i][amount];
        }
        
    int coinChange(vector& coins, int amount) {
        int n = coins.size();
        vector<vector> dp(n, vector(amount+1, INT_MAX/2));
        // 1 对coins[0][0~amoumt]做初始化
        for(int i=0; i<=amount; i++){
            if (i % coins[0] == 0) dp[0][i] = i/coins[0];
        }
        // 2 遍历
        for(int i=1; i<n; i++){
            for(int j=0; j<=amount; j++){
                if (j < coins[i]) dp[i][j] = dp[i-1][j]; else dp[i][j] = min(dp[i-1][j], dp[i][j-coins[i]]+1); } } return dp[n-1][amount] >= INT_MAX/2?-1:dp[n-1][amount];
    }
};

2.2.4 空间压缩

class Solution {
public:
    int dfs(int i, int amount, vector& coins, vector<vector>& dp){
            if (i < 0){ if (amount == 0) return 0; else return INT_MAX/2; } if (coins[i] > amount) return dfs(i-1, amount, coins, dp);
            if (dp[i][amount] != -1) return dp[i][amount];
            dp[i][amount] = min(dfs(i-1, amount, coins, dp), dfs(i, amount-coins[i], coins, dp)+1);
            return dp[i][amount];
        }
        
    int coinChange(vector& coins, int amount) {
        int n = coins.size();
        vector<vector> dp(2, vector(amount+1, INT_MAX/2));
        // 1 对coins[0][0~amoumt]做初始化
        for(int i=0; i<=amount; i++){
            if (i % coins[0] == 0) dp[0][i] = i/coins[0];
        }
        // 2 遍历
        for(int i=1; i<n; i++){
            for(int j=0; j<=amount; j++){
                if (j < coins[i]) dp[i%2][j] = dp[(i-1)%2][j]; else dp[i%2][j] = min(dp[(i-1)%2][j], dp[i%2][j-coins[i]]+1); } } return dp[(n-1)%2][amount] >= INT_MAX/2?-1:dp[(n-1)%2][amount];
    }
};

2.3 真题：单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

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

示例 1：

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

2.3.1 回溯法 – 超时

2.3.2 动态规划

2.4 真题：完全平方数

2.5 真题：组合总和IV

2.6 真题：零钱兑换II

3 变形题目