-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path322.cpp
More file actions
32 lines (32 loc) · 1000 Bytes
/
322.cpp
File metadata and controls
32 lines (32 loc) · 1000 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
// Author: btjanaka (Bryon Tjanaka)
// Problem: (Leetcode) 322
// Title: Coin Change
// Link: https://leetcode.com/problems/coin-change
// Idea: See code comments.
// Difficulty: medium
// Tags: dynamic-programming
class Solution {
public:
// Build a dp table where each index represents the minimum amount of coins to
// get to that amount. Then return the coins at the amount index.
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) return 0;
int dp[amount + 1];
memset(dp, 0, sizeof(dp));
for (int i = 0; i <= amount; ++i) {
if (i == 0 || dp[i] > 0) {
for (int j = 0; j < coins.size(); ++j) {
int next_val = i + coins[j];
if (next_val > 0 && next_val <= amount) {
if (dp[next_val] == 0) {
dp[next_val] = dp[i] + 1;
} else {
dp[next_val] = min(dp[i] + 1, dp[next_val]);
}
}
}
}
}
return dp[amount] == 0 ? -1 : dp[amount];
}
};