lecxe's blog

By lecxe, history, 16 months ago, In English

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?

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

| Write comment?