LeetCode 518 - Coin Change 2


https://leetcode.com/problems/coin-change-2
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-space
dp[i][j] : the number of combinations to make up amount j by using the first i types of coins
State transition:
  1. not using the ith coin, only using the first i-1 coins to make up amount j, then we have dp[i-1][j] ways.
  2. using the ith coin, since we can use unlimited same coin, we need to know how many way to make up amount j - coins[i]by using first i coins(including ith), which is dp[i][j-coins[i]]
Initializationdp[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];
    }
http://www.cnblogs.com/hexsix/p/6412298.html
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]
http://bookshadow.com/weblog/2017/02/12/leetcode-coin-change-2/
动态规划(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)
比如用面值{1, 2, 5}的硬币组成总额5元的不重复排列共9种,分别为:

[1,1,1,1,1] [1,1,1,2] [1,1,2,1] [1,2,1,1] [2,1,1,1] [1,2,2] [2,1,2] [2,2,1] [5]
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
  1.     public int change(int amount, int[] coins) {  
  2.         int[] table=new int[amount+1];  
  3.         table[0]=1;  
  4.         for(int i=0;i<coins.length;i++){  
  5.             int temp=coins[i];  
  6.             for(int j=0;j<amount+1;j++){  
  7.                 if(j-coins[i]>=0){  
  8.                     table[j]+=table[j-coins[i]];  
  9.                 }  
  10.             }  
  11.         }  
  12.         return table[amount];  
  13.     } 
http://wangsc.ga/posts/20170212-leetcode-dp/
public int change(int amount, int[] coins) {
if (amount == 0) return 1;
int[] dp = new int[amount+1];
for (int dom: coins) {
if (dom > amount) continue;
dp[dom] += 1;
for (int i = dom+1; i < amount+1; i ++) {
dp[i] += dp[i - dom];
}
}
return dp[amount];
}

https://medium.com/@HERMAN_WU_89422/coin-change-2-5fcb427524e8
  1. 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.
  2. For initialization: D[i][0] = 1, because amount of 0 can be composed by not choosing anything;
  3. 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];
    }
https://leetcode.com/problems/coin-change-2/discuss/141076/Logical-Thinking-with-Clear-Java-Code
dp[i] as the number of combinations that make up total amount i for 0 <= i <= amount
Final 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] >= 0
Please 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:
dp[i] = dp[i - coins[0]*1] + dp[i - coins[0]*2] + ... + dp[i - coins[coins[0]*k] if i - coins[0]*k >= 0
dp[i] = dp[i - coins[1]*1] + dp[i - coins[1]*2] + ... + dp[i - coins[coins[1]*k] if i - coins[1]*k >= 0
...
dp[i] = dp[i - coins[j]*1] + dp[i - coins[j]*2] + ... + dp[i - coins[coins[j]*k] if i - coins[j]*k >= 0
j is the number of coin denominations.

Can you explain why by having the outer loop be the amount, there are duplicates? I am not sure I am understanding the logic.
    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.
  1.     public int change(int amount, int[] coins) {  
  2.         Arrays.sort(coins);  
  3.         if(coins.length==0){  
  4.             if(amount==0){  
  5.                 return 1;  
  6.             }  
  7.             return 0;  
  8.         }  
  9.         int temp=coins[coins.length-1];  
  10.         help(amount,coins,temp);  
  11.         return count;  
  12.     }  
  13.     int count=0;  
  14.     private void help(int amount, int[] coins,int mark){  
  15.         if(amount==0){  
  16.             count++;  
  17.             return;  
  18.         }else if(amount<0){  
  19.             return;  
  20.         }  
  21.         for(int i=0;i<coins.length;i++){  
  22.             if(mark>=coins[i]){  
  23.                 int temp=coins[i];  
  24.                 int tempamount=amount-temp;  
  25.                 help( tempamount,  coins, temp);  
  26.             }  
  27.         }  
  28.     } 

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
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 )
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);
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);
        }
    }
X. 
because in the second one, you would get duplicate combinations, like amount 5 could be amount 4 (which has comb of 2+2), plus another coin 1, Also it could be amount 3 (which has comb of 1+2), plus another coin 2. suppose our coins are 1,2. So (2,2,1) and (1,2,2) are duplicates.

The first one is calculating assuming the order of coins doesn't matter. The second one takes the order of coins into account. They give different answers
扩展思考:将上述代码中的循环顺序对调,即为求不同硬币的排列数(Permutation)
比如用面值{1, 2, 5}的硬币组成总额5元的不重复排列共9种,分别为:

[1,1,1,1,1] [1,1,1,2] [1,1,2,1] [1,2,1,1] [2,1,1,1] [1,2,2] [2,1,2] [2,2,1] [5]
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]

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts