硬币兑换动态规划问题自顶向下记忆法

Question

我目前正在研究leetcode上的硬币兑换动态规划问题--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

我试图实现一种自上而下的记忆方法，在这种方法中，我保留了一个长度数量的数组，其中每个索引表示我可以用来生成该数量的最小硬币数量。

以下是我的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上超过了时间限制。

这是做动态规划的错误方法吗？如果是这样，你能解释一下哪里错了吗？

非常感谢你提前。

Answer 1

这是我的解决方案版本。这也很容易理解！

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];
    }
}

Answer 2

您的dp[amount]数组仍将对其没有解决方案的所有金额进行递归，即，如果dp[amount]小于0，这将返回INT_MAX，dp[amount]将返回INT_MAX。但您正在检查dp[amount]是否=INT_MAX则只返回dp[amount]值。这就是为什么。