leetcode-Coin Change

题目: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.

有几点需要特殊考虑:
(1)amount = 0,这种情况输出0,而不是-1;
(2)amount < Min(coins[i])无法达到amount,输出-1.

状态转移方程:
dp[i][j]:使用前i种硬币凑成j元使用的最少硬币个数

dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i]] + 1);(j >= coins[i])

code:

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int len = coins.length;
        if(amount == 0) return 0;
        int dp[] = new int[amount + 1];
        dp[0] = 0;
        
        for(int i = 0; i <= amount; i++){
            //not Integer.MAX_VALUE, or dp[i] + 1 < 0;
            dp[i] = Integer.MAX_VALUE - 1;
        }
        for(int i = 0; i < len; i++){
            //if coins[i] > amount, will not update the value 
            if(coins[i] <= amount) dp[coins[i]] = 1;
        }
        
        for(int i = 0; i < len; i++){
            //**j from 0->amount  
            for(int j = 0; j <= amount; j++){
                if(j >= coins[i] && dp[j - coins[i]] >= 0) dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        if(dp[amount] >= Integer.MAX_VALUE - 1) return -1;
        else return dp[amount];
    }
}

这道题属于完全背包,使用滚动数组优化空间。内层循环顺序遍历。因为此时的dp[j]表示的就是当下第i轮凑出j元的情况,如果是0-1背包的话内层循环需要逆序遍历,因为dp[j]表示的是上一轮,(i - 1)轮凑出j元的情况。见下一题。

题目大意:还是给定数组coins[n]表示n种硬币的面额,和一个整数目标值amount, 现在要求出能凑出amount不同的方法数,完全背包和0-1背包各写一种。

状态转移方程:
dpi:使用前i种硬币凑成j元钱不同的方法数;
0-1背包:dp[i][j] += dp[i - 1][j - coins[i]];
完全背包:dp[i][j] += dp[i][j - coins[i]];
使用滚动数组优化空间后,0-1背包内层循环逆序,完全背包内层循环顺序

code:

public class CoinSolution{
    public int getWithDuplicate(int[] coins, int amount){
        int dp[] = new int[amount + 1];
        dp[0] = 1;
        for(int v : coins){
            for(int i = 0; i <= amount; i++){
                if(i - v >= 0) dp[i] += dp[i - v];
            }
        }
        return dp[amount];
    }
    
    public int getWithOutDuplicate(int[] coins, int amount){
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int v : coins){
            for(int i = amount; i >= 0; i--){
                if(i - v >= 0) dp[i] += dp[i - v];
            }
        }
        return dp[amount];
    }
    
    public int MethodJudge(int[] coins, int amount, boolean duplicate){
        if(duplicate) return getWithDuplicate(coins, amount);
        else return getWithOutDuplicate(coins, amount);
    }
    
    public static void main(String[] args){
        int[] coins = {1, 2, 3, 4};
        int target = 7;
        CoinSolution CS = new CoinSolution();
        int result1 = CS.MethodJudge(coins, target, true);
        int result2 = CS.MethodJudge(coins, target, false);
        System.out.println("Number of Methods to get amount with duplicate are: " + result1);
        System.out.println("Number of Methods to get amount without duplicate are: " + result2);
    }
}

result:
Number of Methods to get amount with duplicate are: 11
Number of Methods to get amount without duplicate are: 2

评论

暂无评论