Skip to content

Backpack Problem VIII

Description

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example I

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example II

Input: coins = [2], amount = 3
Output: -1

Question

Transform Function

for(int i = 1; i <= m; i++) {
    for(int j = 1; j <= n; j++) {
        dp[i][j] = dp[i - 1][j];
        for(int k = 1; k * coins[i - 1] <= j; k++) {
            dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k * coins[i - 1]] + k);
        }
    }
}

Template

class Solution {
    public int coinChange(int[] coins, int amount) {
        int m = coins.length, n = amount;
        int[][] dp = new int[m + 1][n + 1];
        for(int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
        for(int i = 0; i <= m; i++) dp[i][0] = 0;

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j];
                for(int k = 0; k * coins[i - 1] <= j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k * coins[i - 1]] + k);
                }
            }
        }
        return dp[m][n] == Integer.MAX_VALUE / 2 ? -1 : dp[m][n];
    }
}

Optimize Analysis

dp[i][j] = Math.min(dp[i - 1][j - k * v[i - 1]] + k | k >= 0)
dp[i][j] = Math.min(dp[i - 1][j], min{dp[i - 1][j - k * v[i - 1] + k | k >= 1}
dp[i][j] = Math.min(dp[i - 1][j], min{dp[i - 1][(j - v[i - 1]) - k * v[i - 1] + k | k >= 0} + 1}
dp[i][j] = Math.min(dp[i - 1][j], min{dp[i][j - v[i - 1] + 1}

Optimize I

class Solution {
    public int coinChange(int[] coins, int amount) {
        int m = coins.length, n = amount;
        int[][] dp = new int[m + 1][n + 1];
        for(int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
        for(int i = 0; i <= m; i++) dp[i][0] = 0;

        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(coins[i - 1] <= j) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[m][n] == Integer.MAX_VALUE / 2 ? -1 : dp[m][n];
    }
}

Optimize II

class Solution {
    public int coinChange(int[] coins, int amount) {
        int m = coins.length, n = amount;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;
        for(int i = 1; i <= m; i++) {
            for(int j = coins[i - 1]; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }
        return dp[n] == Integer.MAX_VALUE / 2 ? -1 : dp[n];
    }
}

Optimize III

class Solution {
     public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;
        for(int i = 1; i <= amount; i++) {
            for(int coin : coins) {
                if(i < coin) continue;
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE / 2 ? -1 : dp[amount];
    }
}