《硬币找零2》为什么这个DP实现效率不够高?

问题描述 投票:0回答:1

我正在研究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);
    }
}

方法上有一些细微差别,但我看不出有什么重大区别。有什么区别可以解释为什么我的实施效率不够高?

java algorithm data-structures dynamic-programming memoization
1个回答
0
投票

第一个版本没有将值写入

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

要激活记忆功能,请将

return
语句更改为:

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

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

© www.soinside.com 2019 - 2024. All rights reserved.