knapsack O(mn) time O(m) space
问题是累加到amount最少需要多少个coin
假设最终是a0 + a1 + a2 + … + ak = amount
最后一步：ak是最后一个coin（可能是任何一种币值coins[j]）
之前一步：a0 + a1 + a2 + … + ak-1 = amount - ak
问题变成：求累加到amount - ak最少需要多少个coin
从f[amount]变成f[amount - ak]，f[i]表示累加到i最少需要多少个coin
状态转移方程：f[i] = min(f[i-coins[j]] + 1) where 0 <= j < n && i >= coins[j]
初始条件：f[0] = 0
最终要求的：f[amount]
边界条件：如果某个f[x]不能由任何coin组合，则其值为INT_MAX（也可以用amount + 1来代替避免overflow）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<int> f(amount + 1, INT_MAX);
f[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int j = 0; j < n; ++j) {
if (i >= coins[j] && f[i - coins[j]] != INT_MAX) {
f[i] = min(f[i], f[i - coins[j]] + 1);
}
}
}
return f[amount] == INT_MAX ? -1 : f[amount];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<int> f(amount + 1, amount + 1);
f[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int j = 0; j < n; ++j) {
if (i >= coins[j]) {
f[i] = min(f[i], f[i - coins[j]] + 1);
}
}
}
return f[amount] >= amount + 1 ? -1 : f[amount];
}
};
|
knapsack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> f(amount + 1, amount + 1);
f[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (int c : coins) {
if (i >= c) {
f[i] = min(f[i], f[i - c] + 1);
}
}
}
return f[amount] > amount ? -1 : f[amount];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> f(amount + 1, amount + 1);
f[0] = 0;
for (int c : coins) {
for (int i = c; i <= amount; ++i) {
f[i] = min(f[i], f[i - c] + 1);
}
}
return f[amount] > amount ? -1 : f[amount];
}
};
|