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

Автор purple_dreams, история, 7 лет назад, По-английски

This problem has a dp solution. DP table can be dp[900][200000] so that is MLE. But there is an observation that level i depends only on level i-1 so dp[2][200000] is sufficient. My question is how to implement this in top down approach with memoization. Is it possible in such questions to write a top down approach or we have to go with bottom up. Thank you.

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

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Yes, bottom up is necessary in this case. This is one of the drawbacks of Top down with memoization approach.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you. I always find top down with memoization a bit more easy. So i was thinking if that is possible in such cases. But now I will see the bottom up approach. Thanks.