Codeforcer's blog

Need Help in resolving TLE in DP with memo and iterative.
By Codeforcer, history, 4 years ago, In English

Why do some solutions containing dp with memoization result in TLE but the same iterative version always passes? I have had this doubt for quite a while.

For example this problem : https://codeforces.net/contest/628/problem/D

DP+Memo->TLE

Checking the editorial they have done the same thing just iterative.

So my questions are this :

->What should be a good practice to write dp memoized or iterative?

->Can every memoized dp problem be converted to iterative ?

->What exactly goes wrong with memoized versions getting TLE'd ?

->How to resolve such TLE's ?

Thanks!

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

Comments Comments (7)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

state of your dp is kind of $$$O(n^2)$$$ and for each state you are running a loop which is $$$O(n)$$$ and hence total time complexity would be $$$O(n^3)$$$ which will result in TLE. Editorial solution is $$$O(n^2)$$$. So you might optimize your recursive dp or it might not be possible to do so in recursive. Also using recursive/iterative depends on the problem and the observations you have made.

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

You're passing string x by value, it creates a copy everytime

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

    this is definitely it.

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

    Wow I thought it was ok to just pass strings and arrays like that..that definitely worked and also ended up a bit faster then the iterative version lol...thanks to you!

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

      it's ok to pass arrays. it just sends the pointer

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

    Also I read somewhere that the order in which matrices are multiplied matters a lot when accessing memory, so how to decide which dimensions to put first in dp ?

    → Reply