两种动态规划解法超时问题解析：LeetCode凑数问题

这是LeetCode上的一道题：给定无限数量的1、2、6面值硬币，以及2枚4面值硬币，求凑出总和n的组合数（组合不考虑顺序），结果取模10^{9+7。约束条件为1<=n<=10}5。

我写的第一种解法代码运行超时，但第二种解法能正常通过。

第一种解法代码：

vector<int> temp{1,2,6};
class Solution {
public:
    long long getTotalNumberOfWays(int n,int index,vector<vector<long long>>& dp){
        if(n==0){
            return 1;
        }
        if(n<0 || index>2){
            return 0;
        }
        if(dp[index][n]!=-1){
            return dp[index][n];
        }
        long long totalWaysWithoutFour = 0;
        int newN = n;
        while(newN>=0){
            totalWaysWithoutFour += getTotalNumberOfWays(newN,index+1,dp);
            newN-=temp[index];
        }
        return dp[index][n] = totalWaysWithoutFour;
    }
    int numberOfWays(int n) {
        vector<vector<long long>> dp(3,vector<long long>(n+1,-1));
        return (int)(getTotalNumberOfWays(n,0,dp) + getTotalNumberOfWays(n-4,0,dp) + getTotalNumberOfWays(n-8,0,dp))%((long long)pow(10,9)+7);
    }
};

第二种解法代码：

vector<int> temp{1,2,6};
class Solution {
public:
    long long getTotalNumberOfWays(int n,int index,vector<vector<long long>>& dp){
        if(n==0){
            return 1;
        }
        if(n<0 || index>2){
            return 0;
        }
        if(dp[index][n]!=-1){
            return dp[index][n];
        }
        long long totalWaysWithoutFour = 0;
        return dp[index][n] = ((getTotalNumberOfWays(n-temp[index],index,dp)) + (getTotalNumberOfWays(n,index+1,dp)));
    }
    int numberOfWays(int n) {
        vector<vector<long long>> dp(3,vector<long long>(n+1,-1));
        return (getTotalNumberOfWays(n,0,dp) + getTotalNumberOfWays(n-4,0,dp) + getTotalNumberOfWays(n-8,0,dp))%((long long)(pow(10,9)+7));
    }
};

我原以为两种解法时间复杂度相同，这个假设错了吗？如果不是，为什么第一种会超时？

你的假设是错误的，两种解法的时间复杂度完全不同：

• 第二种解法的时间复杂度：
  这是典型的记忆化背包递推，每个状态dp[index][n]只会被计算一次。总共有3种硬币（1、2、6），n最大是1e5，总状态数为31e5=3e5。每个状态仅需两次递归调用（取当前硬币/不取当前硬币），且调用后会直接缓存结果，时间复杂度为**O(3n)**，属于线性级别，完全能处理1e5的规模。

• 第一种解法的时间复杂度：
  第一种解法用循环枚举当前硬币的使用次数，比如面对面值1的硬币，当n=1e5时，循环会执行1e5+1次，每次都调用getTotalNumberOfWays(newN, index+1, dp)。虽然有缓存，但第一次计算dp[0][1e5]时，会触发1e5次对dp[1][...]的调用，其中很多dp[1][k]又会触发k/2次对dp[2][...]的调用，实际时间复杂度达到**O(n²)**级别。当n=1e5时，n²是1e10，完全超出时间限制，必然超时。

举个简单例子：计算dp[0][n]时，第一种方法要循环n+1次，每次调用dp[1][n - k*1]；而第二种方法只需要dp[0][n-1] + dp[1][n]，其中dp[0][n-1]已经被之前的计算缓存过，无需重复枚举。

另外，第一种解法的循环枚举会导致大量重复的递归调用（即便最终会被缓存，第一次计算的开销也已经过大），而第二种解法的递推式是背包问题的最优状态转移方式，彻底避免了冗余计算。

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