leetcode动态规划—背包系列（一）

leetcode 474

题目描述：在计算机界中，我们总是追求用有限的资源获取最大的收益。
现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。

你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。

这是一道01背包的变种题，有两个背包大小，0 的数量和 1 的数量。

/*
这个题最重要的是找到物品 和 容量。
换个思路：
A:如果题目是给你一个序列，里面存的是由0组成的字符串，每个字符串的长度不一定，但是都由0组成，给你m个0.求这m个0最多可以装多少个字符串？
B:如果题目给你一个序列，里面存了好多个字符串，每个字符串代表一个物品，长度越长代表物品越沉，背包最大承载量为100，求最多能装多少个物品？

这就熟悉了->01背包
题目就是换了个思路，两维了。一方面要考虑0的情况，一方面要考虑1的情况。
物品没有变，是strs
容量有两个，m和n，要都满足。

动态转移方程
for(0..strs.size)
 for(m...0)
  for(n...0)
    dp[i][j] = max(dp[i][j], dp[i-0数量][j-1数量]+1)

*/

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        if (strs.empty() || (m <= 0 && n <= 0)) return 0;
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        for (auto str : strs) {
            int zero_cnt = 0, one_cnt = 0;          
            for (auto ch : str) {
                if (ch == '0') zero_cnt++;
                else one_cnt++;
            }
            
            for (int i = m; i >= 0; --i) {
               for (int j = n; j >= 0; --j) {
                   if (i >= zero_cnt && j >= one_cnt)
                       dp[i][j] = max(dp[i][j], dp[i-zero_cnt][j-one_cnt] + 1);
               }
            }
        }
        return dp[m][n];
    }
};

leetcode 518

题目描述：给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

完全背包问题，使用 dp 记录可达成目标的组合数目。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1);
        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];
        
    }
};

leetcode 322

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

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

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins)
            if (coin <= i)
                dp[i] = min(dp[i], dp[i - coin] + 1);
    }
    return dp[amount] > amount ? -1 : dp[amount];
}