Java solution with explanation


  • 0
    Z
    //  Recurrence formular 
    //  dp(i) - minimum coins needed to form i  
    //  dp(c) = min( dp(c - coins[0]), dp(c - coins[1]), dp(c - coins[2]), 
    //               ..., dp(c - coins[coins.length - 1]) ) + 1; 
    //             - we can find the minimum coins needed by choosing among sub-problmes.
    
    public class Solution {
        public int coinChange(int[] coins, int amount) {
            int n = coins.length;
            int[] dp = new int[amount+1]; 
            int min = 0;
            Arrays.fill(dp, Integer.MAX_VALUE);
            
            dp[0] = 0;
            
            for( int c = 1; c <= amount; c++){
                min = Integer.MAX_VALUE;
                for( int i = 0; i < n; i++){
                    if(c >= coins[i] && dp[c - coins[i]] != Integer.MAX_VALUE)
                        min = Math.min(min, dp[c - coins[i]] + 1);
                }
                dp[c] = min;
            }
            if(dp[amount] == Integer.MAX_VALUE)
                return -1;
            else
                return dp[amount];
        }
    }
    
    

    Think of it as an unbounded knapsack problem.


Log in to reply
 

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