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];
}
