LeetCode 518. Coin Change II：为何该动态规划实现超时？

问题背景 #

给定不同面额的硬币数组coins和总金额amount，返回组成该金额的组合数（每种硬币可无限使用）。以下两段递归+动态规划代码逻辑等价，但第一段在输入amount=500、coins=[3,5,7,8,9,10,11]时触发超时，第二段可正常运行，现分析效率差异原因。

第一段代码（超时） #

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

效率差异核心原因 #

两段代码逻辑本质等价，但递归调用路径和状态计算方式的差异，导致第一段产生大量额外开销：

1. 状态依赖逻辑不同

   • 第一段采用「选或不选」分支：dp[i][sum] = 选当前硬币的组合数 + 不选当前硬币的组合数，即dp[i][sum] = dp[i][sum-arr[i]] + dp[i+1][sum]。
   • 第二段直接累加分支：dp[start][sum] = 累加从start开始选每个硬币的组合数，即dp[start][sum] = sum(dp[i][sum-arr[i]] for i from start to len(coins)-1)。

2. 冗余中间状态的计算
   第一段需要计算大量无意义的中间状态（比如dp[1][500]、dp[2][500]...dp[6][500]），每个中间状态又会触发自身的「选/不选」递归，带来额外的函数调用和栈操作开销。
   第二段直接跳过这些中间状态，仅计算必要的子状态并累加，避免了冗余的递归调用。

3. 递归栈开销差异
   第一段的递归会不断深入「不选当前硬币」的分支，栈深度增加，且每个状态需要两次递归调用；第二段仅针对「选当前硬币」的子状态递归，无额外分支，栈操作更高效。

简言之，第一段因冗余中间状态的计算导致递归调用次数剧增，在大金额输入下触发超时，而第二段的直接累加方式规避了这些额外开销。

内容的提问来源于stack exchange，提问作者Paurab Bhattacharjee