剑指offer103：最少的硬币数目

题目：

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例一：

输入：coins = [1, 2, 5], amount = 11

输出：3

解释：11 = 5 + 5 + 1

示例二：

输入：coins = [2], amount = 3

输出：-1

示例三：

输入：coins = [1], amount = 0

输出：0

示例四：

输入：coins = [1], amount = 1

输出：1

示例五：

输入：coins = [1], amount = 2

输出：2

分析：

将每种面额的硬币看成一种物品，而将目标金额看成背包的容量，那么这个问题等价于求将背包放满时物品的最少件数，值得注意的时这里每种面额的硬币可以使用任意多次，因此这个问题不再是0-1背包问题了，而是一个无界背包问题。（也叫完全背包问题）

用函数f(i,j)表示前i种硬币（coins[0,…,i-1]）凑出总额为j需要的硬币的最少数目，当使用0枚标号为i-1的硬币时，f(i,j)=f(i-1,j)，当使用1枚标号为i-1的硬币时，f(i,j)等于f(i-1,j-coins[i-1])+1,以此类推当使用k枚标号为i-1的硬币时，f(i,j)等于f(i-1,j-kcoins[i-1])+k（用前i-1种硬币凑出总额j-kcoins[i-1]需要的最少硬币数目，再假设k枚标号为i-1的硬币），由于目标时求出硬币数目的最小值，因此f(i,j)是上述所有情况的最小值：

如果硬币有n种，目标总额为t，那么f(n,t)就是问题的解。

当j=0时也就是总额为0时，f（i，0）=0，也就是从前i种硬币中选出0个硬币，使总额等于0.当i等于0且j大于0时，即用0种硬币凑出大于0的总额显然不可能因此可以用一个特殊值代替。

第二种思路：

之前相当于横着从右往左计算，这种方式类似从上往下算，算完一列再算下一列，用函数f(i)表示凑出总额为i的硬币需要的最少数目，需要注意的是，这个函数只有一个参数i表示硬币的总额，如果目标总额为t那么f(t)就是整个问题的解。

代码：

import java.util.Arrays;

public class CoinChange {
//    第一种思路
    public int coinChange1(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for (int coin : coins) {
            for (int j = amount; j >=1; j--) {
                for (int k = 1; k*coin <=j; k++) {
                    dp[j] = Math.min(dp[j],dp[j-k*coin]+k);
                }
            }
        }
        return dp[amount] > amount ?-1:dp[amount];
    }
//    第二种思路
//
    public int coinChange2(int[] coins, int amount){
        int[] dp = new int[amount+1];
//        i代表总额，dp[i]代表凑出总额为i的最少硬币数目
        for (int i = 1; i <=amount; i++) {
            dp[i] = amount+1;
            for (int coin:coins){
//                如果总额度大于等于该硬币的值
                if (i>=coin){
                    dp[i] = Math.min(dp[i],dp[i-coin]+1);
                }
            }
        }
        return dp[amount]>amount ?-1:dp[amount];
    }
}