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

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 上遇到了 Time Limit Exceeded。

这是一种错误的动态规划方法吗？如果有，请说明哪里错了？

在此先感谢您。

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，这将 return INT_MAX , dp[数量] 将 INT_MAX。但是你正在检查如果 dp[amount] !=INT_MAX 那么只有 return dp[amount] 值。这就是为什么TTE。

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

Coin change dynamic-programming question top-down memoization approach

dynamic-programming

memoization

coin-change