lvisbl_'s blog

By lvisbl_, history, 3 days ago, In English

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

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it