Coin change DP solution to keep track of coins


http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=148775&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
题目是这样的,输入是一个int amount 和 vector<int> coins,分别表示总货币量、各个coin的价值量,要求以最少的coin个数凑齐总货币量。 (大家应该都熟悉吧?入门级的DP题目。。)
然后输出的是每种货币的数目,vector<int> nums。. 鍥磋鎴戜滑@1point 3 acres
举例:  amount  = 40, coins = [1,5,15,25],输出[0,1,1,1]. 鍥磋鎴戜滑@1point 3 acres
再举例: amount  = 40, coins = [1,5,20,25],输出[0,0,2,0]

关键是刚开始没怎么听清楚,问了好几遍才确认,自己也是太紧张了。然后先确认了几个细节要求:
都是整数?是的
最后是要凑齐exact的目标数值amount?是的
会有无解的情况吗?默认总会有价值为“1”的coin. Waral 鍗氬鏈夋洿澶氭枃绔�,

我刚开始想着用backtracking+贪心来做,先sort,再用最贵的coin开始凑,后来一想不对,应该bottom up用dp,转移方程就是dp = min(dp[i-1]+1, dp[i-coins[j]]+j) for all j from 1~coins.size()-1;

然后写着写着就迷糊了,忘记目标不是coin的总数而是每个coin的个数。。。事实上,我写完之后(当时是只记录dp,即总数),他说yes I think this works. 然后follow up问如果amount很大怎么办。
我想着想着发现只要keep tracking dp 里后面 coins.size() 数量的dp即可,only store the dp, dp[i-coins[1]]....., dp[i-coins[coins.size()-1]]. more info on 1point3acres.com
他说好的,很好,又问了总体的时间空间复杂度。(好了到目前为止我们两个估计都忘记了刚开始要的是各个coin的个数。。。)

然后闲聊了几句,他突然问我,噢等一下,我们要求的不是总数。。。我就突然紧张了,想了一会后,在每个dp的循环里加了个stack用来记录插入过的coin index,如果dp更新的话就把前面
的那个pop出来回滚回去,再把新的弄进来,感觉好像可以。。。

http://stackoverflow.com/questions/20185590/coin-change-dp-solution-to-keep-track-of-coins
public static int minimumNumberOfWays(int []deno, int amount){
    int dp[] = new int[amount+1];
    dp[0]=0;
    int []prevCoin = new int[amount+1];  
    for(int j=1;j<=amount;j++){
        dp[j]=Integer.MAX_VALUE;
        for(int i=0;i<deno.length;i++){
            if(deno[i]<=j && (1+dp[j-deno[i]] < dp[j]) ){               
                dp[j]=1+dp[j-deno[i]];
                prevCoin[j]=deno[i];
            }                   
        }
    }

    int result = dp[amount];
    List<Integer> coinsAdded = new ArrayList<Integer>();
    for(int i=amount;i>=1;){
        coinsAdded.add(prevCoin[i]);
        int j=i;
        i=amount-prevCoin[i];
        amount = amount - prevCoin[j];
    }
    Integer [] coins = coinsAdded.toArray(new Integer[coinsAdded.size()]);
    System.out.println( Arrays.toString(coins)); 
You don't need the first dimension of your dp. You can use an array with only one dimension - the sum of all used coins. Then you can simply store the index of your last used coin for each state of your dp. What I mean is something like:
int[] dp = new int[n];
int[] usedCoin = new int[n];

for (int i=0; i < n; ++i) {
    dp[i] = -1; // state not reached
    usedCoin[i] = -1;
}

dp[0] = 0; // initial state -- we can have sum 0 without any coins
for (int coinId = 0; coinId < m; coinId++)
    for (int sum = 0; sum + denom[coinId] < n; sum++) {
        int newSum = sum + denom[coinId];
        if (dp[newSum] == -1 || dp[newSum] > 1 + dp[sum]) {
            dp[newSum] = 1 + dp[sum];
            usedCoin[newSum] = coinId;
        }
    }
If you want to find a concrete decomposition with minimum amount of coins, you can do something like:
int sum = changeAmount;
System.out.println("The used coins are:");
while (usedCoin[sum] != -1) {
    System.out.print(denom[ usedCoin[sum] ].toString() + " ");
    sum -= denom[ usedCoin[sum] ];
}
Related: Coin change problem with limit on number of coins of each denomination

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