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 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, will not update the value             if(coins[i] amount              for(int j = 0; 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 = 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

关键字：背包问题

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！