[Question] Get TLE when switch the dimension of the DP array

Revision en2, by lvisbl_, 2024-06-12 14:25:39

Hello mates, I'm trying to solve this DP question Coin Combinations II from CSES: https://cses.fi/problemset/task/1636/

Initially, I define an array dp[i][j]: meaning number of ways to form sum i, starting choosing coins from j-th index. And this solution using this DP array get me TLE.

But if I switch the two dimension, array dp[i][j]: number of ways to form sum j, starting choosing coins from i-th index. This solution give me accepted. But why?

Note:

  • Two solution is 99% the same the only different is that I switch two dimensions.

  • Sum i at most 10^6 and there are at most 10^2 coins.

Thank in advance.

Accepted code
TLE code
Tags dynamic programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English lvisbl_ 2024-06-12 14:25:39 13
en1 English lvisbl_ 2024-06-12 14:23:08 2995 Initial revision (published)