《硬币找零2》：为什么这种动态规划实现效率不够高？

Question

我正在研究LeetCode，问题518。硬币找零 II ：

您将获得一个表示不同面额硬币的整数数组

coins

和一个表示总金额的整数

amount

。

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

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

但是对于以下输入，它会失败并出现“超出时间限制”错误：

amount = 500
coins = [3,5,7,8,9,10,11]

我有另一个不会遇到这个超时的实现：

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

第一个版本没有将找到的结果写入

dp

，因此它无法从记忆中受益。由于测试将包括多达 500 个不同的硬币，金额高达 5000 个，因此使用相同参数调用该函数的次数将是巨大的。

要激活记忆功能，请将

return

语句更改为：

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

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