题目：
原本是 BFS 写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <vector>
#include <queue>
using std::vector;
using std::queue;
class Solution {
public:
int coinChange(vector<int> &coins, int amount)
{
int i, j, n = coins.size();
int curr;
vector<int> dp(amount + 1, -1);
dp[amount] = 0;
queue<int> que;
que.push(amount);
while (!que.empty()) {
curr = que.front();
que.pop();
for (i = 0; i < n; i++) {
if (curr - coins[i] >= 0 &&
dp[curr - coins[i]] == -1) {
dp[curr - coins[i]] = dp[curr] + 1;
que.push(curr - coins[i]);
if (curr - coins[i] == 0) {
return dp[0];
}
}
}
}
return dp[0];
}
};
|
经典背包问题 dp，以 amount=3,为例
$$
F(3) = \min\big(F(3 - c_1), F(3 - c_2), F(3 - c_3)\big) + 1
$$
$$
= \min\big(F(3 - 1), F(3 - 2), F(3 - 3)\big) + 1
$$
$$
= \min\big(F(2), F(1), F(0)\big) + 1
$$
$$
= \min(1, 1, 0) + 1
$$
$$
= 1
$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <vector>
#include <climits>
using std::vector;
class Solution {
public:
int coinChange(vector<int> &coins, int amount)
{
int i, j, n = coins.size();
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (i = 1; i <= amount; i++) {
for (j = 0; j < n; j++) {
if (i - coins[j] >= 0 &&
dp[i - coins[j]] != INT_MAX) {
dp[i] = std::min(dp[i - coins[j]] + 1,
dp[i]);
}
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
};
|
