rmz's blog

Have you encountered this before ?
By rmz, history, 2 years 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

Comments Comments (3)
| Write comment?
»
2 years ago, hide # |
 
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