-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCoinChange2.cpp
More file actions
38 lines (36 loc) · 997 Bytes
/
CoinChange2.cpp
File metadata and controls
38 lines (36 loc) · 997 Bytes
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
34
35
36
37
38
// 第一种解法
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<vector<int>> dp(coins.size() + 1, vector<int>(amount + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= coins.size(); i++)
{
dp[i][0] = 1;
for (int j = 1; j <= amount; j++)
{
if (j - coins[i - 1] >= 0)
dp[i][j] = dp[i][j - coins[i - 1]] + dp[i - 1][j];
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[coins.size()][amount];
}
};
// 第二种解法
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int i = 0; i < coins.size(); i++)
{
for (int j = 1; j <= amount; j++)
{
dp[j] = dp[j] + (j - coins[i] >= 0 ? dp[j - coins[i]] : 0);
}
}
return dp[amount];
}
};