This is one of those problems where the clean idea matters more than the amount of code. For 322. Coin Change, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: dynamic programming, backtracking.
The notes already sitting in the source point us in the right direction:
- DP
- TLE
- 58 / 182 test cases passed.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are coinChange, count.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//DP
02//TLE
03//58 / 182 test cases passed.
04class Solution {
05public:
06 int coinChange(vector<int>& coins, int amount) {
07 if(amount == 0) return 0;
08 //padding ahead
09 vector<int> count(amount+1, INT_MAX);
10
11 //base case
12 for(int coin : coins){
13 //to ensure it won't exceed the array's size
14 if(coin <= amount) count[coin] = 1;
15 }
16
17 // for(int i = 1; i <= amount; i++){
18 // cout << i << ", " << count[i] << " | ";
19 // }
20 // cout << endl;
21
22 for(int i = 1; i <= amount; i++){
23 for(int j = 1; j <= i/2; j++){
24 if(count[j] == INT_MAX || count[i-j] == INT_MAX){
25 //skip this split
26 continue;
27 }else{
28 count[i] = min(count[i], count[j] + count[i-j]);
29 }
30 }
31 // cout << i << ", " << count[i] << endl;
32 }
33 // cout << "===========" << endl;
34
35 return count[amount] == INT_MAX ? -1 : count[amount];
36 }
37};
38
39//DP
40//Runtime: 124 ms, faster than 29.29% of C++ online submissions for Coin Change.
41//Memory Usage: 14.1 MB, less than 27.45% of C++ online submissions for Coin Change.
42class Solution {
43public:
44 int coinChange(vector<int>& coins, int amount) {
45 if(amount == 0) return 0;
46 //padding ahead
47 vector<int> count(amount+1, INT_MAX);
48
49 //base case
50 for(int coin : coins){
51 //to ensure it won't exceed the array's size
52 if(coin <= amount) count[coin] = 1;
53 }
54
55 // for(int i = 1; i <= amount; i++){
56 // cout << i << ", " << count[i] << " | ";
57 // }
58 // cout << endl;
59
60 for(int i = 1; i <= amount; i++){
61 for(int coin : coins){
62 if(i < coin) continue;
63 if(count[i-coin] == INT_MAX) continue;
64 count[i] = min(count[i], count[i-coin]+1);
65 }
66 // cout << i << ", " << count[i] << endl;
67 }
68 // cout << "===========" << endl;
69
70 return count[amount] == INT_MAX ? -1 : count[amount];
71 }
72};
73
74//DP, more concise
75//Runtime: 120 ms, faster than 33.17% of C++ online submissions for Coin Change.
76//Memory Usage: 14 MB, less than 31.37% of C++ online submissions for Coin Change.
77class Solution {
78public:
79 int coinChange(vector<int>& coins, int amount) {
80 //we use "amount+1" in replace of INT_MAX
81 //padding ahead
82 vector<int> dp(amount+1, amount+1);
83 dp[0] = 0;
84
85 for(int i = 1; i <= amount; i++){
86 for(int coin : coins){
87 if(coin > i) continue;
88 dp[i] = min(dp[i], dp[i-coin]+1);
89 }
90 }
91
92 return dp[amount] > amount ? -1 : dp[amount];
93 }
94};
95
96//recursion
97//Runtime: 1128 ms, faster than 5.02% of C++ online submissions for Coin Change.
98//Memory Usage: 66.5 MB, less than 5.88% of C++ online submissions for Coin Change.
99class Solution {
100public:
101 unordered_map<int, int> memo;
102
103 int coinChange(vector<int>& coins, int amount) {
104 if(memo.find(amount) != memo.end()) return memo[amount];
105
106 if(amount == 0){
107 memo[amount] = 0;
108 return memo[0];
109 }
110
111 if(coins.size() > 0 && amount < *min_element(coins.begin(), coins.end())){
112 memo[amount] = -1;
113 return memo[amount];
114 }
115
116 int count = INT_MAX;
117 for(int coin : coins){
118 //edge case
119 if(amount == coin){
120 memo[amount] = 1;
121 return memo[amount];
122 }
123 int remainCount = coinChange(coins, amount-coin);
124 if(remainCount == -1) continue;
125 // cout << coin << " + " << amount - coin << " : " << 1 + remainCount << endl;
126 count = min(count, 1 + remainCount);
127 }
128
129 if(count == INT_MAX) count = -1;
130
131 memo[amount] = count;
132
133 return memo[amount];
134 }
135};
136
137//Approach #2 (Dynamic programming - Top down)
138//recursion, more concise
139//Runtime: 968 ms, faster than 5.02% of C++ online submissions for Coin Change.
140//Memory Usage: 61.6 MB, less than 9.80% of C++ online submissions for Coin Change.
141//time: O(S*n), S(amount): recursion depth, n(coins.size()): the for loop
142//space: O(S), the memo
143class Solution {
144public:
145 unordered_map<int, int> memo;
146
147 int coinChange(vector<int>& coins, int amount) {
148 //edge case of "amount = coins[?]" can be replaced with this
149 if(amount == 0) return 0;
150 if(amount < 0) return -1;
151 if(memo.find(amount) != memo.end()) return memo[amount];
152
153 int cost = INT_MAX;
154 for(int coin : coins){
155 int res = coinChange(coins, amount-coin);
156 if(res >= 0) cost = min(cost, 1+res);
157 }
158
159 memo[amount] = (cost == INT_MAX) ? -1 : cost;
160 return memo[amount];
161 }
162};
163
164//backtrack
165//TLE
166//57 / 182 test cases passed.
167//time: S is amount, ci means ith element in coins, S/c0 * S/c1 * S/cn-1 => O(S^n)
168//space: O(n), recursion depth
169class Solution {
170public:
171 int coinChange(int idxCoin, vector<int>& coins, int amount){
172 if(amount == 0) return 0;
173 if(idxCoin >= coins.size() || amount < 0) return -1;
174
175 int minCost = INT_MAX;
176 for(int i = 0; i <= amount/coins[idxCoin]; i++){
177 //we use "i" coins[idxCoin]
178 if(amount >= i * coins[idxCoin]){
179 int res = coinChange(idxCoin+1, coins, amount-i*coins[idxCoin]);
180 if(res == -1) continue;
181 minCost = min(minCost, i + res);
182 }
183 }
184
185 return (minCost == INT_MAX) ? -1 : minCost;
186 };
187
188 int coinChange(vector<int>& coins, int amount) {
189 return coinChange(0, coins, amount);
190 }
191};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.