rmz's blog

Have you encountered this before ?
By rmz, history, 8 months ago, In English

In this problem I made a dp solution that gets MLE.

Then i added this piece of code.

    for (int i = 1 ; i < n ; i++){
        depee(i,0);
    }

Surprisingly, it worked and i got AC.

can you explain what happened?

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it
The Nice lines of the code
→ Reply
»
8 months ago, # |
  Vote: I like it +14 Vote: I do not like it

I think your recursion calls itself too much if you do it all in one go -depee(10000000) would call depee(9999999) which calls depee(9999998) ... depee(0), and the program consumes alot of memory to keep track of all this recursion. Your second submission avoids this issue. When depee(n) is called, it calls depee(n-1) which was previously solved, and thus fewer recursive calls need to be kept track of at a time.

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

    a great example why to use bottom-up if can(which we can here)

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

    Thanks for your explanation, I get it now.

    → Reply