CSES Coin Combinations II - top-down DP gets a time limit

Problems and Contests
#1

Hello guys. I was solving CSES - Coin Combinations II problem and end up with a solution as followed, but for a reason, I got time limit on several test cases.

Here is my solution:

#include <bits/stdc++.h>

using namespace std;

using lli = int64_t;
using pii = pair < int, int > ;
using vint = vector < int > ;
using triple = pair < int, pii > ;

const int MX = 1e6 + 5;
const int MXC = 105;
const int MOD = 1e9 + 7;

int n;
int coins[MXC];
int dp[MX][MXC];

int solution(int x, int k) {
    if (x < 0 || k < 0) return 0;

    if (x == 0) return dp[x][k] = 1;

    if (dp[x][k] != -1) return dp[x][k];

    return dp[x][k] = (solution(x - coins[k], k) + solution(x, k - 1)) % MOD;
}

void solve() {
    int x;
    cin >> n >> x;

    for (int i = 0; i < n; i++) cin >> coins[i];

    sort(coins, coins + n);

    for (int i = 0; i <= x; i++) {
        fill(dp[i], dp[i] + n, -1);
    }

    cout << solution(x, n - 1);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
        cout << '\n';
    }

    return 0;
}

But I don’t get it why? My solution’s time complexity must be O(nx), and nx must be ok for this problem, but why do I get a time limit? What’s wrong with this code? I want to learn and prevent this type of error again.

#2

In general, top-down is likely to be slower than bottom-up since calling functions comes with overhead. (You can look into the materials for any class on computer systems for the reasoning behind it.)

Ordinarily we don’t really care about the overhead of function calls, because it’s usually insignificant compared to the other work done by the program.

But in this case, there isn’t really any other work done by the program–you do ~10^8 additions, ~10^8 modulos, ~10^8 array accesses and ~10^8 function calls.

Replacing the calls with array accesses will then speed up the program significantly.

#3

top down have extra function calling overheads
May be they want iterative solution.
I just solved this.

i hope this helps you with a better idea :stuck_out_tongue:

void solve()
{
    int n, x;
    cin >> n >> x;
 
    vi arr(n);
    cin >> arr;
   
    vi dp(x + 1, 0);
 
    dp[0] = 1;
    for (int i = 0; i < n; i++)
    {
 
        for (int sum = 0; sum <= x; sum++)
        {
 
            if (sum >= arr[i])
            {
                dp[sum] += dp[sum - arr[i]];
                dp[sum]%=mod;
            }
        }
    }
    cout<<dp[x]<<endl;
}