Is there some trick to convert DFS+memo into dp

Правка en1, от retr0coderxyz, 2020-05-25 20:20:22

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)[https://leetcode.com/problems/profitable-schemes/]

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!

Теги #dynamic programing

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский retr0coderxyz 2020-05-25 20:28:38 174
en2 Английский retr0coderxyz 2020-05-25 20:20:51 8
en1 Английский retr0coderxyz 2020-05-25 20:20:22 2182 Initial revision (published)