Repository navigation
Expand file tree
/
Copy pathcoinChange.cpp
More file actions
103 lines (93 loc) · 3.28 KB
/
Copy pathcoinChange.cpp
File metadata and controls
103 lines (93 loc) · 3.28 KB
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// Source : https://leetcode.com/problems/coin-change/
// Author : Calinescu Valentin, Hao Chen
// Date : 2015-12-28
/***************************************************************************************
*
* You are given coins of different denominations and a total amount of money amount.
* Write a function to compute the fewest number of coins that you need to make up that
* amount. If that amount of money cannot be made up by any combination of the coins,
* return -1.
*
* Example 1:
* coins = [1, 2, 5], amount = 11
* return 3 (11 = 5 + 5 + 1)
*
* Example 2:
* coins = [2], amount = 3
* return -1.
*
* Note:
* You may assume that you have an infinite number of each kind of coin.
*
* Credits:
* Special thanks to @jianchao.li.fighter for adding this problem and creating all test
* cases.
*
***************************************************************************************/
/* Recursive solution - TIME LIMIT ERROR */
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int result = INT_MAX;
if ( amount == 0 ) return 0;
if ( amount < 0 ) return -1;
for (int i=0; i<coins.size(); i++) {
if ( amount - coins[i] < 0 ) continue;
int r = coinChange(coins, amount - coins[i]);
if ( r == -1 ) continue;
if (result > r ) result = r + 1;
}
return result == INT_MAX ? -1 : result;
}
}
/*
* Solution 1 - O(N * amount)
* =========
*
* This problem can be solved using dynamic programming, thus building the optimal
* solution from previous smaller ones. For every coin of value t and every sum of money
* i the sum can be traced back to a previous sum i - t that was already computed and uses
* the smallest number of coins possible. This way we can construct every sum i as the
* minimum of all these previous sums for every coin value. To be sure we'll find a minimum
* we can populate the solution vector with an amount bigger than the maximum possible,
* which is amount + 1(when the sum is made up of only coins of value 1). The only exception
* is sol[0] which is 0 as we need 0 coins to have a sum of 0. In the end we need to look
* if the program found a solution in sol[amount] or it remained the same, in which case we
* can return -1.
*
*/
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int sol[amount + 1];
sol[0] = 0;
for(int i = 1; i <= amount; i++)
sol[i] = amount + 1;
for(int i = 0; i < coins.size(); i++)
{
for(int j = coins[i]; j <= amount; j++)
sol[j] = min(sol[j], sol[j - coins[i]] + 1);
}
if(sol[amount] != amount + 1)
return sol[amount];
else
return -1;
}
};
//Another DP implmentation, same idea above
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
const int MAX = amount +1;
vector<int> dp(amount+1, MAX);
dp[0]=0;
for(int i=1; i<=amount; i++) {
for (int j=0; j<coins.size(); j++){
if (i >= coins[j]) {
dp[i] = min( dp[i], dp[i-coins[j]] + 1 );
}
}
}
return dp[amount]==MAX ? -1 : dp[amount];
}
};