硬币变化动态规划问题自上而下的记忆法

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

你的dpamount数组仍然会递归所有那些它没有解决方案的金额，例如，如果dpamount小于0，这将返回INT_MAX，dpamount将INT_MAX。但是您正在检查，如果dpamount !=INT_MAX则只返回dpmont值。这就是为什么TTE。

Answer 2

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

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