DP approach O(nk), Also includes trace(though not required in the problem)


  • 0
    R

    I saw this really amazing video on this problem. Took most of the idea from that. The solution is very clean.

    public class Solution {
        public int coinChange(int[] coins, int amount) {
            /*
                This problem uses DP, 
                There are 2 arrays to be maintained 
                    1. Minimum number of coins to reach a particular index value -- here we initialize the array size equal to amount + 1
                    2. From where the last move was played .. to trace (extra)
            */
            
            
            int[] T = new int[amount + 1];
            int[] R = new int[amount + 1];
            
            // initialize
            int len = T.length;
            
            for (int i = 0; i < len; i++) {
                T[i] = Integer.MAX_VALUE - 1;
                R[i] = -1;
            }
            
            T[0] = 0; // To reach 0 no coins are required!
            
            
            for (int j = 0; j < coins.length; j++) {
                for (int i = 0; i < len; i++) {
                    if (i >= coins[j]) {
                        if (T[i] > 1 + T[i - coins[j]]) {
                            T[i] = 1 + T[i - coins[j]];
                            R[i] = j; 
                        }
                    }
                }
            }
            
            printTheTrace(R, coins);
            
            
            if (T[amount] == Integer.MAX_VALUE - 1) {
                return - 1;
            } else {
                return T[amount];
            }
            
        }
        
        
        private void printTheTrace(int[] R, int[] coins) {
            if (R[R.length - 1] == -1) {
                System.out.println("The is no way we can get that!");
                return;
            }
            
            int amount = R.length - 1;
            while (amount != 0) {
                int j = R[amount];
                System.out.print(coins[j] + " ");
                amount -= coins[j];
            }
        }
    }
    
    
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.