Leetcode背包问题

完全背包问题

LC 518. 零钱兑换 II

题意：几种无限数量的硬币，凑成amount的方案数，方案是无序的，即1+2 和 2+1算同一种
题解：

方法一：经典背包解法

dp[i][j]表示前i种物品凑出j的方案数，考虑第i个选与不选两种情况，其中选的时候，再考虑选择第i个物品的次数。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        int dp[n+1][amount+1];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;

        for(int i = 1;i <= n;i++) {
            for(int j = 0;j <= amount;j++) {
                dp[i][j] = dp[i-1][j];
                for(int k = 1;k*coins[i-1] <= j;k++) {
                    dp[i][j] += dp[i-1][j-k*coins[i-1]];
                }
            }
        }
        return dp[n][amount];
    }
};

方法二：刷表法

拿每个硬币刷一次表，对于1 2 3 5，相当于先只选1，再只选1 2，再只选1 2 3，这样就不用考虑顺序问题。其次，需要从左往右刷，例如枚举2的时候，dp[i-2]已经可能被2刷新过了，dp[i]+=dp[i-2]就行，不需要考虑选多次2，像dp[i]=1+1+2+2+2+2已经被dp[i-2]考虑了
总之，这种方法即限制了顺序，又不用手动枚举coins[i]的次数

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

注意。这里有一个常见的问题，我可以将i和j两个循环交换顺序吗？
不能，交换后相当于，先选一次1 2 3 5，这样选择100次，显然没有考虑顺序问题，有大量重复
但是，有时候是可以交换的，也就是与方案的顺序无关时，例如求最小的方案数（即最少的硬币数），例如 LC691. 贴纸拼词 和 下面的零钱兑换I

LC 322. 零钱兑换

题解：也是刷表法，但是可以交换顺序

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int dp[amount+1];
        memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0;
        for(int coin : coins) {
            for(int i = 0;i+coin <= amount;i++) {
                dp[i+coin] = min(dp[i+coin], dp[i]+1);
            }
        }
        int res = dp[amount];
        return res==0x3f3f3f3f ? -1 : dp[amount];
    }
};

01背包

也就是最经典的背包，每个物品只能选一次，dp[i][j]表示前i个凑成j的最大收益，dp[i][j] = min(dp[i-1][j], dp[i-1][j-cap[i]] + val[i])

LC 416. 分割等和子集

题解：dp[i][j] 表示前i个能否凑出和为j。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for(int num : nums)  sum += num;
        if(sum%2)  return 0;
        int dp[n+1][sum+1];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for(int i = 1;i <= n;i++) {
            for(int j = 0;j <= sum;j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1])  dp[i][j] |= dp[i-1][j-nums[i-1]];
            }
        }
        return dp[n][sum/2];
    }
};

多维背包

LC 474. 一和零

题解：多维背包，其实和普通背包思想是一模一样的，只是增加了一维限制。dp[i][j][k] 表示前i个0的个数不超过j且1的个数不超过k的最大元素个数。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int t) {
        int n = strs.size();
        int cnt[n+1][2];
        memset(cnt, 0, sizeof(cnt));
        for(int i = 0;i < n;i++) {
            for(char ch : strs[i]) {
                if(ch == '0')  cnt[i][0]++;
                else  cnt[i][1]++;
            }
        }
        int dp[n+1][m+1][t+1];
        memset(dp, 0, sizeof(dp));
        // dp[0][]
        for(int i = 1;i <= n;i++) {
            for(int j = 0;j <= m;j++) {
                for(int k = 0;k <= t;k++) {
                    dp[i][j][k] = dp[i-1][j][k];   // 不选
                    if(j>= cnt[i-1][0] && k >= cnt[i-1][1]) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-cnt[i-1][0]][k-cnt[i-1][1]]+1);  // 选
                    }
                }
            }
        }
        return dp[n][m][t];
    }
};

LC 879. 盈利计划

题解：多维背包，dp[i][j][k]表示前i个工作 人员不超过j 利润不少于k 的计划数
由于我们定义的第三维是工作利润至少为 k 而不是工作利润恰好为 k，因此上述状态转移方程中右侧的第三维是 max(0, k - profit[i])，而不是k-profit[i]，因为当k-profit[i]<0时还不如取0

const int mod = 1e9+7;
class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int m = group.size();
        int dp[m+1][n+1][minProfit+1];
        memset(dp, 0, sizeof(dp));
        for(int i = 0;i <= n;i++)  dp[0][i][0] = 1;
        for(int i = 1;i <= m;i++) {
            for(int j = 0;j <= n;j++) {
                for(int k = 0;k <= minProfit;k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j>= group[i-1]) {
                        dp[i][j][k] = (dp[i][j][k] + dp[i-1][j-group[i-1]][max(0,k-profit[i-1])]) % mod;
                    }
                }
            }
        }
        return dp[m][n][minProfit];
    }
};

注意，某限制维刚好等于j 和 小于等于j，这两者的状态转移方程是一模一样的，只是初始化不同，
例如，刚好等于j，memset(dp, 0, sizeof(dp)); dp[0][0]=1
小于等于j，memset(dp, 0x3f, sizeof(dp)); dp[0][0]=1

方法总结

1. 能否凑成j，选或运算
2. 求最少/最多元素，选min/max
3. 求方案数，选加法
4. 刚好等于和小于等于，只有初始化时不同
5. 元素无限求方案数时，先枚举元素，避免重复
6. 某维大于等于j，max(0, j-cost[i])