[HELP] Dp optimization (CSES coin combinations 2)

Правка en1, от lecxe, 2023-07-25 09:33:44

Question https://cses.fi/problemset/task/1636/

My code: https://pastebin.com/Ex76qD5f


I know for some problems where in dp state, the transitions go from (i,j) -> (i+1, j) or (i, j) -> (i-1, j)
in this case we can make the dp storage as dp[2][maxJ] instead of dp[maxI][maxJ]

But is there a way I can do the same when I have already written the code in recursive fashion?

or make just few changes to code so to apply this (i.e dp[2][maxJ]) optimization, instead of writing the iterative code again to apply the optimization.

Теги dp, cses_dp, help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский lecxe 2023-07-25 10:25:38 129
en1 Английский lecxe 2023-07-25 09:33:44 682 Initial revision (published)