Coin combinations II

Revision en3, by WayBig, 2023-05-15 17:14:24

I am facing Time Limit Exceeded in the problem Coin Combinations II of cses.


Full code

My approach: We define rec(x, r) as the number of ordered ways to make a sum x by using up to rth coin (0-indexing). Now we are iterating from the last coin. We can either take rth coin and add up rec(x — c[r], r) to our answer or we can not take the rth coin and simply add up rec(x, r-1) (the answer by taking up to (r-1)th coin). So we have:

dp[i][j] = dp[i - c[j]][j] + dp[i][j - 1]

We also do dp[i][j] %= MOD to prevent overflow.

What could be the possible reason for Time Limit Exceeded? Thank you.

UPD: One person in the comments told that it is because constraints on CSES are tight and that's why recursion might give a TLE on CSES. I think that answers the question.

UPD: This is the exact reason for the TLE

Tags cses, dp, time limit exceeded, cses_dp


  Rev. Lang. By When Δ Comment
en3 English WayBig 2023-05-15 17:14:24 108
en2 English WayBig 2023-05-14 08:26:25 183
en1 English WayBig 2023-05-14 07:51:12 1414 Initial revision (published)