https://leetcode.com/problems/coin-change-2
https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-518-coin-change-2/
http://bookshadow.com/weblog/2017/02/12/leetcode-coin-change-2/
http://blog.csdn.net/qq_27262609/article/details/64126895
https://medium.com/@HERMAN_WU_89422/coin-change-2-5fcb427524e8
X. DP O(n) space
https://leetcode.com/problems/coin-change-2/discuss/99212/Knapsack-problem-Java-solution-with-thinking-process-O(nm)-Time-and-O(m)-Space
Final State:
State Transformation:
Please note that the outer loop should be about
X.
http://www.techiedelight.com/total-possible-solutions-linear-equation-k-variables/
Finally, we return total ways by including or excluding current coefficient. The base case of the recursion is when solution is found (i.e. rhs becomes 0) or the solution doesn’t exist (when no coefficients are left or rhs becomes negative).
X. DFS
https://segmentfault.com/a/1190000017056368 - TLE
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.
Note: You can assume that
- 0 <= amount <= 5000
- 1 <= coin <= 5000
- the number of coins is less than 500
- the answer is guaranteed to fit into signed 32-bit integer
Example 1:
Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
Example 2:
Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10] Output: 1
https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-518-coin-change-2/
Transition 1:
Let us use dp[i][j] to denote the number of ways to sum up to amount j using first i kind of coins.
dp[i][j] = dp[i – 1][j – coin] + dp[i – 1][j – 2* coin] + …
Time complexity: O(n*amount^2) TLE
Space complexity: O(n*amount) -> O(amount)
Transition 2:
Let us use dp[i] to denote the number of ways to sum up to amount i.
dp[i + coin] += dp[i]
Time complexity: O(n*amount)
Space complexity: O(amount)
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins)
for (int i = 0; i <= amount - coin; ++i)
dp[i + coin] += dp[i];
return dp[amount];
}
https://leetcode.com/problems/coin-change-2/discuss/99212/knapsack-problem-java-solution-with-thinking-process-onm-time-and-om-spacedp[i][j] : the number of combinations to make up amount j by using the first i types of coinsState transition:- not using the
ith coin, only using the firsti-1coins to make up amountj, then we havedp[i-1][j]ways. - using the
ith coin, since we can use unlimited same coin, we need to know how many way to make up amountj - coins[i]by using firsticoins(includingith), which isdp[i][j-coins[i]]
Initialization: dp[i][0] = 1
Once you figure out all these, it's easy to write out the code:
public int change(int amount, int[] coins) {
int[][] dp = new int[coins.length+1][amount+1];
dp[0][0] = 1;
for (int i = 1; i <= coins.length; i++) {
dp[i][0] = 1;
for (int j = 1; j <= amount; j++) {
dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j-coins[i-1]] : 0);
}
}
return dp[coins.length][amount];
}
Now we can see that
dp[i][j] only rely on dp[i-1][j] and dp[i][j-coins[i]], then we can optimize the space by only using one-dimension array. public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i-coin];
}
}
return dp[amount];
}dp[i]表示总额为i时的方案数.
转移方程: dp[i] = Σdp[i - coins[j]]; 表示 总额为i时的方案数 = 总额为i-coins[j]的方案数的加和.
记得初始化dp[0] = 1; 表示总额为0时方案数为1.
2 def change(self, amount, coins): 3 """ 4 :type amount: int 5 :type coins: List[int] 6 :rtype: int 7 """ 8 size = len(coins) 9 dp = [1] + [0] * amount 10 for i in range(size): 11 for j in range(amount): 12 if j + coins[i] <= amount: 13 dp[j + coins[i]] += dp[j] 14 return dp[-1]
动态规划（Dynamic Programmin）
状态转移方程见代码
def change(self, amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
dp = [0] * (amount + 1)
dp[0] = 1
for c in coins:
for x in range(c, amount + 1):
dp[x] += dp[x - c]
return dp[amount]
扩展思考：将上述代码中的循环顺序对调，即为求不同硬币的排列数（Permutation）
def change(self, amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
dp = [0] * (amount + 1)
dp[0] = 1
for x in range(amount + 1):
for c in coins:
if c > x: continue
dp[x] += dp[x - c]
return dp[amount]http://blog.csdn.net/qq_27262609/article/details/64126895
- public int change(int amount, int[] coins) {
- int[] table=new int[amount+1];
- table[0]=1;
- for(int i=0;i<coins.length;i++){
- int temp=coins[i];
- for(int j=0;j<amount+1;j++){
- if(j-coins[i]>=0){
- table[j]+=table[j-coins[i]];
- }
- }
- }
- return table[amount];
- }
https://medium.com/@HERMAN_WU_89422/coin-change-2-5fcb427524e8
- There are two critical parameters: number of coin kinds and the amount it needs to compose, so we can define D[i][j] = number of combination where i = ith coin kind, j = amount.
- For initialization: D[i][0] = 1, because amount of 0 can be composed by not choosing anything;
- Iterate through i and j, D[i][j] = D[i-1][j] + D[i][j-coins[i]]
| public int change(int amount, int[] coins) { | |
| int[][] results = new int[coins.length + 1][amount + 1]; | |
| results[0][0] = 1; | |
| for (int i = 1; i <= coins.length; i++) { | |
| results[i][0] = 1; | |
| for (int j = 1; j <= amount; j++) { | |
| // if the coin's value is bigger than amount, copy the result from previous row directly. | |
| results[i][j] = results[i-1][j] + (j >= coins[i-1] ? results[i][j - coins[i-1]] : 0); | |
| } | |
| } | |
| return results[coins.length][amount]; | |
| } |
X. DP O(n) space
https://leetcode.com/problems/coin-change-2/discuss/99212/Knapsack-problem-Java-solution-with-thinking-process-O(nm)-Time-and-O(m)-Space
we can see that
dp[i][j] only rely on dp[i-1][j] and dp[i][j-coins[i]], then we can optimize the space by only using one-dimension array. public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i-coin];
}
}
return dp[amount];
}dp[i] as the number of combinations that make up total amount i for 0 <= i <= amountFinal State:
dp[amount]State Transformation:
dp[i] = dp[i - coins[0]] + dp[i - coins[1]] + ... + dp[i - coins[coins.length - 1]] if i - coins[0] >= 0Please note that the outer loop should be about
coins, while the inner loop should be about amount. Or else, there may be duplicates in the result, e.g. for input: amount = 5, coins = [1, 2, 5], it counts [2, 2, 1] and [2, 1, 2] as two different combinations, so it will return 9 rather than 5. All in all, the order of coins doesn't matterin this case, so we set it as the outer loop.
It would be more clear (why there is no duplicate) if the state transformation is written this way:
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int j = 0; j < coins.length; j++) {
for (int i = 1; i <= amount; i++) {
if (i - coins[j] >= 0) {
dp[i] += dp[i - coins[j]];
}
}
}
return dp[amount];
}X.
- public int change(int amount, int[] coins) {
- Arrays.sort(coins);
- if(coins.length==0){
- if(amount==0){
- return 1;
- }
- return 0;
- }
- int temp=coins[coins.length-1];
- help(amount,coins,temp);
- return count;
- }
- int count=0;
- private void help(int amount, int[] coins,int mark){
- if(amount==0){
- count++;
- return;
- }else if(amount<0){
- return;
- }
- for(int i=0;i<coins.length;i++){
- if(mark>=coins[i]){
- int temp=coins[i];
- int tempamount=amount-temp;
- help( tempamount, coins, temp);
- }
- }
- }
http://www.techiedelight.com/total-possible-solutions-linear-equation-k-variables/
Given a linear equation of k variables, count total number of possible solutions of it.
For example,
Input: coeff = {1, 3, 5, 7}, rhs = 8
Output: Total number of solutions are 6
Output: Total number of solutions are 6
Above input represents the equation a + 3b + 5c + 7d = 8.
( a = 1, b = 0, c = 0, d = 1 )
( a = 0, b = 1, c = 1, d = 0 )
( a = 2, b = 2, c = 0, d = 0 )
( a = 3, b = 0, c = 1, d = 0 )
( a = 5, b = 1, c = 0, d = 0 )
( a = 8, b = 0, c = 0, d = 0 )
( a = 0, b = 1, c = 1, d = 0 )
( a = 2, b = 2, c = 0, d = 0 )
( a = 3, b = 0, c = 1, d = 0 )
( a = 5, b = 1, c = 0, d = 0 )
( a = 8, b = 0, c = 0, d = 0 )
The problem is similar to finding total number of ways to get the denomination of coins. Here, coefficients of an equation can be considered as coins denominations and RHS of an equation can be considered as desired change. Let us begin by recursively defining the problem –
count(coeff, k, rhs) = count(coeff, k, rhs-coeff[k]) + count(coeff, k-1, rhs);
count(coeff, k, rhs) = count(coeff, k, rhs-coeff[k]) + count(coeff, k-1, rhs);
That is, for each coefficient of a variable
- We include current coefficient coeff[k] in solution and recurse with remaining value (rhs-coeff[k]).
- We exclude current coefficient coeff[k] from solution and recurse for remaining coefficients (k-1).
Finally, we return total ways by including or excluding current coefficient. The base case of the recursion is when solution is found (i.e. rhs becomes 0) or the solution doesn’t exist (when no coefficients are left or rhs becomes negative).
public static int count(int coeff[], int k, int rhs)
{
// if rhs becomes 0, solution is found
if (rhs == 0)
return 1;
// return 0 if rhs becomes negative or no coefficient is left
if (rhs < 0 || k < 0)
return 0;
// Case 1. include current coefficient coeff[k] in solution and
// recurse with remaining value (rhs - coeff[k])
int include = count(coeff, k, rhs - coeff[k]);
// Case 2. exclude current coefficient coeff[k] from solution and
// recurse for remaining coefficients (k - 1)
int exclude = count(coeff, k - 1, rhs);
// return total ways by including or excluding current coefficient
return include + exclude;
}
X. DFS
https://segmentfault.com/a/1190000017056368 - TLE
int count = 0;
public int change(int amount, int[] coins) {
if (amount == 0) return 1;
dfs(coins, 0, 0, amount);
return count;
}
private void dfs(int[] coins, int start, int sum, int amount) {
if (start == coins.length) return;
if (sum == amount) {
count++;
return;
}
for (int i = start; i < coins.length; i++) {
if (coins[i] + sum > amount) continue;
else dfs(coins, i, sum+coins[i], amount);
}
}
扩展思考：将上述代码中的循环顺序对调，即为求不同硬币的排列数（Permutation）
def change(self, amount, coins):
dp = [0] * (amount + 1)
dp[0] = 1
for x in range(amount + 1):
for c in coins:
if c > x: continue
dp[x] += dp[x - c]
return dp[amount]