[HELP] Dp optimization (CSES coin combinations 2)

Revision en2, by lecxe, 2023-07-25 10:25:38

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.

NOTE: I want to know if I can apply this optimization for a general case? Or it is necessary to write iterative code to apply it?

Tags dp, cses_dp, help

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English lecxe 2023-07-25 10:25:38 129
en1 English lecxe 2023-07-25 09:33:44 682 Initial revision (published)