Is there some trick to convert DFS+memo into dp

Revision en3, by retr0coderxyz, 2020-05-25 20:28:38

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!

P.S. Please Dont downvote this blog guys as some people have extension to hide bad blogs. Once I get an answer you can downvote it to your hearts content. Thanks :)

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)