Understanding dynamic programming timeouts with 2 different solutions

Question

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 .

Answer 1

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).

Answer 2

I understand this is not exactly an answer to the question, but it seems worth noting that since we only need to count the solutions and not to list them, this can be solved in O(1) constant time by just using some arithmetics.

Obviously if we only had 1s the only solution wouuld be to use n 1s.

Enter 2s. We have a base solution with all 2s (plus one 1 if n is odd). Then we can expand zero or more 2s in pairs of 1s, so we have exactly n / 2 + 1 solutions.

Now for the 6s. Again we have a base solution with all 6s (plus some 2s or 1s if n is not a multiple of six, but let's forget about that for now). And again we can expand zero or more 6s in triples of 2s which in turn can be expanded in 1s as we already saw. When we expand zero 6s we have one solution, when we expand one we have four solutions (because three 2s give four solutions), and so on. The series goes like 1, 4, 7, 10, ... and we must sum these values, so we get 1, 5, 12, 22, .... This is a known seqwuence that can be generated by 3 * i * (i + 1) / 2 + i + 1, so we simply assign i = n / 6 to have the number of solutions for n, when n is a multiple of six.

We still have to deal with the remainder, r = n % 6, when n is not a multiple of six. If r is one, nothing changes. If it is two or three, we'll have to add one solution for each possible number of expansions of the 6s (because for instance with one expansion we had three 2s and thus four solutions, but now we have four 2s, so five solutions); if it is four or five, we'll add two solutions for each expansion. So we must add r / 2 * (i + 1) to our previous result.

Let's sum the values we get for n, n - 4, and n - 8, when appropriate, to handle the 4s and we're done.