purple_dreams's blog

Question in dp problem http://codeforces.com/problemset/problem/478/D

By purple_dreams, history, 7 years ago, In English

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.

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply