求问两个code的区别在哪？322. Coin change

一个int array，里面的数是硬币的面值，求最少数量的硬币组成一个amount

1.

2.



一个答案是对的，每次从第一个数查看；一个是错的，每次从自己开始查看。为什么是错的啊？实在想不明白。

改成这样就能过。因为你会skip掉一些state。但第2个code永远都是从0开始，所以不会skip 一些state。
class Solution {
    int dp[][];
    public int coinChange(int[] coins, int amount) {
        dp = new int[amount + 1][coins.length + 1];
        return dfs(coins, amount, 0);
    }
   
    public int dfs(int coins[], int amount, int start) {
        if(amount < 0) {
            return -1;
        }
        if(amount == 0) {
            return 0;
        }
        
        if(dp[amount][start] != 0) return dp[amount][start];
        
        int res = Integer.MAX_VALUE;
        for(int i = start; i < coins.length; i++) {
            int x = dfs(coins, amount - coins, i);
            if(x >= 0) {
                res = Math.min(res, 1 + x);
            }
        }
        if(res == Integer.MAX_VALUE)res = -1;
        return dp[amount][start] = res;
    }
}

66j 发表于 2022-2-1 13:02
改成这样就能过。因为你会skip掉一些state。但第2个code永远都是从0开始，所以不会skip 一些state。
class ...

确实过了，能帮我举个具体的例子吗？例如skip了哪个state？

66j 发表于 2022-2-1 13:02
改成这样就能过。因为你会skip掉一些state。但第2个code永远都是从0开始，所以不会skip 一些state。
class ...

我以为已经找过这个combination就不用再查看了，但是是错的，我理解上是不是有什么重大误区？

pnwair 发表于 2022-2-1 23:26
我以为已经找过这个combination就不用再查看了，但是是错的，我理解上是不是有什么重大误区？

因为你dp[amount] !=0 就return，所以有可能被一个不是最优的给记录掉

pnwair 发表于 2022-2-1 23:26
我以为已经找过这个combination就不用再查看了，但是是错的，我理解上是不是有什么重大误区？

但是第二个你每个都重新check一下，所以不会有这种情况。但建议你用我那种，把所有state 都列出来，就不容易出错

66j 发表于 2022-2-1 22:31
但是第二个你每个都重新check一下，所以不会有这种情况。但建议你用我那种，把所有state 都列出来，就不 ...

我画了画图，我那个确实是错误的，还是用你的答案保险，谢谢你的指导。