forked from LeetCode-in-Cpp/LeetCode-in-Cpp
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Solution.cpp
29 lines (27 loc) · 912 Bytes
/
Solution.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
// #Medium #Top_100_Liked_Questions #Array #Dynamic_Programming #Breadth_First_Search
// #Algorithm_II_Day_18_Dynamic_Programming #Dynamic_Programming_I_Day_20
// #Level_2_Day_12_Dynamic_Programming #Big_O_Time_O(m*n)_Space_O(amount)
// #2024_05_22_Time_12_ms_(97.65%)_Space_16_MB_(67.57%)
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; ++i) {
int prev = dp[i - coin];
if (prev > 0) {
if (dp[i] == 0) {
dp[i] = prev + 1;
} else {
dp[i] = min(dp[i], prev + 1);
}
}
}
}
return dp[amount] - 1;
}
};