leetcode-零钱兑换

周末一直在下雨，甚至看天气预报，年前就一直是这样的天气了。不过这样的天气也有好处，反正哪儿也去不了，就在家看看书，也算是难得精心。

题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

示例 1：

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

输出： 3

解释： 11 = 5 + 5 + 1

示例 2：

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

输出： -1

示例 3：

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

输出： 0

示例 4：

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

输出： 1

示例 5：

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

输出： 2

思路

这也是一个背包问题，要求刚好把背包装满，选用尽量少的件数。

定义一个一维数组dp，dp[n]代表总金额为n的情况下，最少的硬币个数，如果无法刚好凑成n，那么可以用一个特殊的固定值。dp[n] = min(dp[n-coin[k]]) + 1

怎么理解呢？

我们可以这么考虑：刚好组成总金额n的硬币中，可能包含coin[0]~coin[len-1]各有ci枚，当然，ci可以是0。如果ci > 0，那么我们可以先去掉这一枚，这样，dp[n] = dp[n-coin[k]] + 1;因为有len枚硬币，这里就可能存在len种情况，所以，dp[n] = min(dp[n-coin[0]]+1...dp[n-coin[len-1]]+1)，整理一下，就得到了上面的状态转移方程。

边界条件，amount为0的时候，我们可以不用任何1枚硬币，所以dp[0] = 0。

另外，对于n无法刚好凑成的情况，本来我们可以初始化dp[n] = Integer.MAX_VALUE，由于有+1这个操作，会导致溢出，所以我们选择把dp[n]初始化成amount+1，因为面值是整数，至少是1，所以对于能凑成的n，硬币个数一定小于amount+1，等于amount+1的，就代表无法凑成。

Java版本代码

class Solution {

    public int coinChange(int[] coins, int amount) {

        int[] dp = new int[amount+1];

        Arrays.fill(dp, amount + 1);

        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {

            for (int coin : coins) {

                if (i >= coin) {

                    dp[i] = Integer.min(dp[i], dp[i-coin] + 1);

                }

            }

        }

        if (dp[amount] > amount) {

            return -1;

        }

        return dp[amount];

    }

}