Java DP solution, idea based on backpack


  • 0
    J

    This is a problem of backpack allowing infinite usage of elements.

        public int coinChange(int[] coins, int amount) {
            if(amount == 0) {
                return 0;
            }
            int len = coins.length;
            int[]dp = new int[amount + 1];
            for(int j = 1; j <= amount; j++) {
                dp[j] = -1;
            }
            for(int i = 1; i <= len; i++) {
                for(int j = coins[i - 1]; j <= amount; j++) {
                    if(dp[j - coins[i - 1]] != -1) {
                        if(dp[j] == -1) {
                            dp[j] = dp[j - coins[i - 1]] + 1;
                        } else {
                            dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
                        }
                        
                    }
                }
            }
            return dp[amount];
        }
    

Log in to reply
 

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