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!
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.
You're passing string
xby value, it creates a copy everytimethis is definitely 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!
it's ok to pass arrays. it just sends the pointer
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 ?
Usually, smaller dimensions should be kept first. Ref