my Classic DP solution -leetcode is to strengthen your coding ability not enjoy the limelight by shorten code or reduce time complicity


  • 0
    G
    public class Solution {
        public int coinChange(int[] coins, int amount) {
        if(amount==0){
            return 0;
        }
        
        int [] dp = new int[amount+1];
        dp[0]=0;
        
        for(int i=1;i<dp.length;i++){
            dp[i] = Integer.MAX_VALUE;
        }
        
        for(int i=0;i<=amount;i++){
            
            for(int coin:coins){
                if(coin<Integer.MAX_VALUE-i){//void some corner case like:[2147483647] 2
                    if(i+coin<=amount){//void out bound
                        if(dp[i]!=Integer.MAX_VALUE){
                            dp[i+coin]=Math.min(dp[i+coin],dp[i]+1);
                        }
                    }
                }
            }
        }
        if(dp[amount]!=Integer.MAX_VALUE){
            return dp[amount];
        }
        else{
            return -1;
        }
        
      }
    }

Log in to reply
 

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