-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
518.cpp
36 lines (33 loc) · 1.03 KB
/
518.cpp
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
__________________________________________________________________________________________________
sample 4 ms submission
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1, 0);
dp[0]=1;
for (int coin : coins) {
for (int i=coin; i<=amount; i++) {
dp[i]+=dp[i-coin];
}
}
return dp.back();
}
};
__________________________________________________________________________________________________
sample 8448 kb submission
class Solution {
public:
int change(int amount, vector<int>& coins) {
int dp[amount+1] = {0};
dp[0] = 1;
for (int i = 0; i < coins.size(); i++) {
for (int j = 1; j < amount+1; j++) {
if (j >= coins[i]) {
dp[j] += dp[j-coins[i]];
}
}
}
return dp[amount];
}
};
__________________________________________________________________________________________________