Блог пользователя lecxe

Автор lecxe, история, 17 месяцев назад, По-английски

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?

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится