Kaleab_Asfaw's blog

CSES — DP Coin Combination II TLE
By Kaleab_Asfaw, history, 4 years ago, In English

Getting TLE with a python solution for Coin Combination problem in here

I know that python is slow ..., but have seen other python users solving it here

My Code

Creating the dp 2D array is even taking much time. Is there a way it can be optimized?

Thanks for taking your time and reading this!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The dp can be 1 dimensional, let c[] be the coins and x the sum, then dp[x] is the answer:

    dp[0]=1;
    for(int a : c) {
        for(int i=0; i+a<=x; i++) {
            dp[i+a]+=dp[i];
            dp[i+a]%=MOD;
        }
    }
→ Reply