Is there some trick to convert DFS+memo into dp

Revision en2, by retr0coderxyz, 2020-05-25 20:20:51

Hello guys,

I have been trying to solve Dp problems. When I read a problem I try to translate it into DFS(recursion) which ends up having TLE, then I simply store the state variables so it passes the time limit. But What I want to learn is that, any trick is there to convert this into iterative DP( As I guess DFS+memo has large constant factor).

For example take this problem: link

TLE Code non memoized
DFS+Memo Passed

So I want to learn a generic technique ( not limited to this problem) to write iterative solutions as No matter how hard I try I am unable to grasp iterative writing method. It would be great if you guys could help me in this. Thank you!

Tags #dynamic programing

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English retr0coderxyz 2020-05-25 20:28:38 174
en2 English retr0coderxyz 2020-05-25 20:20:51 8
en1 English retr0coderxyz 2020-05-25 20:20:22 2182 Initial revision (published)