skpro19's blog

Problem in converting bottom-up dp to recursive dp due to memory limitations
By skpro19, history, 8 years ago, In English

In this question, DIV 2C, Is is possible to solve this using recursive approach without exceeding the memory limit??

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

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

Auto comment: topic has been updated by skpro19 (previous revision, new revision, compare).

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

You don't need to convert it. You can use simple memory optimisation in this question because the current state i depends only on the previous state i-1.

So you can use i%2 instead of i and that would save a lot of memory.

Have a look in this code here: Code

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

    The thing is, I always solve dp problems recursively, so i was wondering will it be possible to solve it in a recursive fashion without exceeding the memory limit? I do understand the bottom up approach though.

    → Reply