Java DynamicProgramming O(NumberCoins*Amount) and memory O(Amount)


  • 0
    D
    public class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0 ) return 0;
    
        int[] buf = new int[amount];
    
        for(int i=0;i<amount;i++){
            buf[i] = Integer.MAX_VALUE;
            
            for(int j=0;j<coins.length;j++){
                if((i+1-coins[j])==0){
                    buf[i] = 1;
                    break;
                }else if((i+1-coins[j])>0){
                    int val = buf[i-coins[j]];
                    if(val!=Integer.MAX_VALUE)
                        buf[i] = Math.min(buf[i],val+1);
                }
            }
        }
    
        return buf[amount-1]==Integer.MAX_VALUE ? -1 : buf[amount-1];
    }
    

    }


Log in to reply
 

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