通过 2 种不同的解决方案了解动态编程超时

Question

问题来自leetcode（链接 - https://leetcode.com/problems/the-number-of-ways-to-make-the-sum/description/）

您有无数个价值为 1、2 和 6 的硬币，而只有 2 个价值为 4 的硬币。

给定一个整数n，返回将n与你拥有的硬币相加的方法的数量。

由于答案可能非常大，因此返回对 109 + 7 求模的结果。

请注意，硬币的顺序并不重要，[2, 2, 3] 与 [2, 3, 2] 相同。

示例1：

输入：n = 4

输出：4

说明：

这里有四种组合：[1, 1, 1, 1], [1, 1, 2], [2, 2], [4]。

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

代码运行良好。 我的理解是第一个和第二个代码具有相同的时间复杂度，如果不是的话，我在这个假设上是错误的吗？为什么第一个代码超时了。

Answer 1

第一个程序具有二次运行时间，而第二个程序具有线性运行时间。

抽象地说，你的第一个程序正在计算：

U(n, index) = sum(U(n-coin*i, index+1) for i=0...n/coin[index])

你的第二个程序正在计算这个：

V(n, index) = V(n, index+1) + V(n-coin[index], index)

并且两者都缓存以前的结果并正确处理边缘情况。

在你的第一个程序（我称之为

U

）中，计算

dp

表中的任何条目都需要Theta（n/coin）时间，即使它需要的所有结果都已经计算出来了。因此，即使有一枚价值 1 的硬币，第一个程序也是二次的。

你的第二个程序没有这个错误——假设之前的结果被缓存，它的时间是O(1)。

由于

dp

的所有元素最终都会被精确计算一次，这意味着您的第一个程序将是

Theta(N²*coins)

，第二个程序将是

Theta(N*coins)

。