硬币找零动态规划问题自顶向下备忘录算法

Question

硬币找零动态规划问题自顶向下备忘录算法

dynamic-programmingmemoizationcoin-change

4

我目前正在力扣上做找零钱动态规划问题 -- https://leetcode.com/problems/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.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1

我尝试使用自顶向下的记忆化方法，其中我保留一个长度为amount的数组，其中每个索引表示我可以使用的最少硬币数来凑成该金额。

以下是我在Java中的代码:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];

        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        int min = coinChange(coins, amount, dp);

        return min == Integer.MAX_VALUE ? -1 : min;
    }

    private int coinChange(int[] coins, int amount, int[] dp) {
        if (amount < 0) {
            return Integer.MAX_VALUE;
        }
        if (amount == 0) {
            return 0;
        }

        if (dp[amount] != Integer.MAX_VALUE) {
            return dp[amount];
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {
            int val = coinChange(coins, amount - coins[i], dp);

            if (val != Integer.MAX_VALUE) {
                min = Math.min(min, val + 1);
            }
        }

        dp[amount] = min;
        return min;
    }
}

我认为这是解决这个问题的正确动态规划方法，但是在LeetCode上却遇到了超时错误。

这种动态规划方法是否错误？如果是，请说明它错在哪里。

非常感谢您的帮助。

- Wonjoo Lee

你可能应该定义你特定的硬币找零问题，而不是假设其他人知道这个问题。同时在问题中提到你使用的编程语言。虽然代码看起来像Java，但其他人可能不知道。 - ThomasMcLeod

@ThomasMcLeod 感谢您的建议！问题的链接已经在那里了，但我也在帖子中包含了问题陈述。我还指出解决方案是用Java编写的。谢谢！ - Wonjoo Lee

我其实有完全相同的代码和问题。 - Mohit Shah

2个回答

1

你的dp [amount]数组仍将为所有那些没有解决方案的金额进行递归，即如果dp [amount]小于0，则会返回INT_MAX，dp [amount]将为INT_MAX。但是您正在检查是否dp [amount]！= INT_MAX，然后才返回dp [amount]值。这就是TTE的原因。

- Been A Long While

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- executable · Accepted Answer

这是我提供的解决方案。这个版本易于理解！

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];

        Arrays.fill(dp, 0);

        int min = coinChange(coins, amount, dp);
        return min;
    }

    private int coinChange(int[] coins, int amount, int[] dp) {
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }

        if (dp[amount]!=0) {
            return dp[amount];
        }

        int minimum = Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {
            int val = coinChange(coins, amount - coins[i], dp);

            if (val >= 0 && val < minimum) {
                minimum = val + 1;
            }
        }
        dp[amount] = (minimum == Integer.MAX_VALUE) ? -1 : minimum;
        return dp[amount];
    }
}