我为leetcode问题“硬币找零2”写了两个解决方案……为什么第一个不起作用而第二个却很好

Question

问题： 给你一个代表不同面额硬币的整数数组硬币和代表总金额的整数金额。

返回组成该金额的组合数。如果任何硬币组合都无法弥补该金额，则返回 0。

您可能会假设您拥有无限数量的每种硬币。

第一个解决方案：

class Solution {
    public int func(int[] arr,int sum,int i,int[][] dp){
        if(i>=arr.length) return 0;
        if(sum==0) return 1;
        if(sum<0) return 0;
        if(dp[i][sum]!=-1) return dp[i][sum];
        else{
            int t=func(arr,sum-arr[i],i,dp);
            int nt=func(arr,sum,i+1,dp);
            return t+nt;
        }
    }
    public int change(int amount, int[] coins) {
        int[][] dp=new int[coins.length][amount+1];
        for(int[] arr:dp){
            Arrays.fill(arr,-1);
        }
        return func(coins,amount,0,dp);
    }
}

第二个解决方案：

class Solution {
    public int func(int[] arr,int sum,int start,int[][] dp){
        if(sum==0) return 1;
        if(sum<0) return 0;
        if(dp[start][sum]!=-1) return dp[start][sum];
        else{
            int s=0;
            for(int i=start;i<arr.length;i++){
                s+=func(arr,sum-arr[i],i,dp);
            }
            return dp[start][sum]= s;
        }
    }
    public int change(int amount, int[] coins) {
        int[][] dp=new int[coins.length][amount+1];
        for(int[] arr:dp){
            Arrays.fill(arr,-1);
        }
        return func(coins,amount,0,dp);
    }
}

为什么第一个代码不正确而第二个代码正确？

Answer 1

第一个实现的问题在这里：

if(i>=arr.length) return 0;

此条件检查是否仍有硬币可供选择，但它忽略了您可能已经达到目标金额并且不再需要更多硬币的可能性。在这种情况下，它会错误地返回 0。

要解决此问题，请更改前两个语句的顺序，以便

sum

检查提前进行：

if(sum==0) return 1;
if(i>=arr.length) return 0;

不相关，但第一个版本没有将值写入

dp

，因此它无法从记忆中受益。要激活它，请将

return

语句更改为：

return dp[i][sum]=t+nt;

...与第二个版本类似。

第二个代码片段在每次选择硬币后执行

sum==0

，并通过其

for

循环处理数组限制，因此它没有第一个版本的错误。