leetCode-322:Coin Change

问题描述

给定一个数组，表示硬币的面额，每种硬币数量不限，给定另一个目标数字，要求使用最小数量的硬币，将其组合起来值等于目标值。找到则返回最小的硬币数量，找不到则返回 -1。题目链接：**点我**

样例输入输出

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

输出：3

解释：硬币组合为 5 + 5 +1

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

输出：-1

问题解法

刚开始想用贪心的算法，按从大到小的排序对每种硬币计算其所需要的数量，但是发现一个问题，贪心找出来的第一个答案可能不是最小硬币的数量，如 coins = [7, 6, 2], amount = 18，用上述贪心算法找到的答案是 7 + 7 + 2 + 2，总共 4 个，但是事实存在更小的硬币组合：6 + 6 + 6，总共 3 个。所以单纯用贪心算法是不能正确求解的。查看题目提示，是用动态规划进行求解。假设 dp[i] 表示用硬币组合 i 金额所需要的最小数量，则 dp[i] = min(dp[i], dp[i - coins[j]] + 1) ，代码如下

class Solution
{
    public int coinChange(int[] coins, int amount)
    {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++)
        {
            for (int j = 0; j < coins.length; j++)
            {
                if (i == coins[j])
                {
                    dp[i] = 1;
                    continue;
                }

                if (i - coins[j] > 0 && dp[i - coins[j]] != -1)
                {
                    if (dp[i] == -1 || dp[i] > dp[i - coins[j]] + 1)
                    {
                        dp[i] = dp[i - coins[j]] + 1;
                    }
                }
            }
        }

        return dp[amount];
    }
}