[HELP] Dp optimization (CSES coin combinations 2)
source link: https://codeforces.com/blog/entry/118616
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[HELP] Dp optimization (CSES coin combinations 2)
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?
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK