Understanding dynamic programming timeouts with 2 different solutions

The problem is from leetcode (link - https://leetcode.com/problems/the-number-of-ways-to-make-the-sum/description/ )

You have an infinite number of coins with values 1, 2, and 6, and only 2 coins with value 4.

Given an integer n, return the number of ways to make the sum of n with the coins you have.

Since the answer may be very large, return it modulo 109 + 7.

Note that the order of the coins doesn't matter and [2, 2, 3] is the same as [2, 3, 2].

Example 1:

Input: n = 4

Output: 4

Explanation:

Here are the four combinations: [1, 1, 1, 1], [1, 1, 2], [2, 2], [4].

Constraints 1 <= n <= 10^5

While i wrote the solution as

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

I am getting timeout on above code . While if i do this

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

The code is passing fine . My understanding was 1st and second code have same time complexity Am i wrong in this assumption if not than why is the first one timing out .

The first program has quadratic runtime, whereas the second program has linear runtime.

Abstractly, your first program is calculating this:

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

And your second program is calculating this:

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

and both are caching previous results and handling edge-cases correctly.

In your first program (which I've called U) it takes Theta(n/coin) time to compute any entry in the dp table, even if all the results it needs are already computed. So even with a single coin of value 1, the first program is quadratic.

Your second program doesn't have this fault -- it's O(1) time assuming previous results are cached.

Since all elements of dp are eventually going to be computed exactly once each, this means that your first program will be Theta(N²*coins) and your second will be Theta(N*coins).

Also, I might write what you've called getTotalNumberOfWays like this, without recursion and without dependencies on globals, and incorporating mod to avoid overflows for larger n:

int getTotalNumberOfWays(int n, int mod, std::vector<int>& coins) {
    if (n < 0) {
        return 0;
    }
    std::vector<int> T(n + 1);
    T[0] = 1;
    for (int c : coins) {
        for (int i = c; i <= n; ++i) T[i] = (T[i - c] + T[i]) % mod;
    }
    return T[n];
}

(it depends on 2*mod <= INT_MAX).