-
Notifications
You must be signed in to change notification settings - Fork 1
/
322_Coin_Change.cpp
69 lines (60 loc) · 1.32 KB
/
322_Coin_Change.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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
[2,5,10,1]
27
Output: 8
Expected: 4
[186,419,83,408]
6249
TLE
*/
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int dp[10000];
class Solution {
public:
int rec(vector<int>& coins, int amount){
if(amount < 0) return -1;
if(amount == 0) return 0;
if(dp[amount] != 0) return dp[amount];
int ans = INT_MAX;
for(int i = 0; i < coins.size(); i++){
if(amount - coins[i] >= 0){
int res = rec(coins, amount - coins[i]);
if(res >= 0 && res < ans) ans = 1 + res;
}
}
if(ans == INT_MAX) ans = -1;
cout << "remaining: " << amount << " ans: " << ans << endl;
return dp[amount] = ans;
}
int coinChange(vector<int>& coins, int amount) {
memset(dp, 0, sizeof(dp));
return rec(coins, amount);
}
};
int main(){
Solution* p;
/*
vector<int> v;
v.push_back(2);
v.push_back(5);
v.push_back(10);
v.push_back(1);
cout << p->coinChange(v, 27) << endl;
*/
/*
vector<int> v;
v.push_back(2);
v.push_back(1);
cout << p->coinChange(v, 999) << endl;
*/
vector<int> v;
v.push_back(186);
v.push_back(419);
v.push_back(83);
v.push_back(408);
cout << p->coinChange(v, 6249) << endl;
return 0;
}