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 :)**

Auto comment: topic has been updated by retr0coderxyz (previous revision, new revision, compare).Auto comment: topic has been updated by retr0coderxyz (previous revision, new revision, compare).Generally Speaking? No, I haven't found any proven systematic method to convert a Recursive approach to Iterative approach.

Technically Speaking? Yeah, There's plenty of insights the recursive solution gives you,

For example

1-You're able to find what values to return in the base cases, and what are the base cases themselves.

2-You're able to find if you need to iterate from 0 -> n or n -> 0, depending on what is calculated in the base case

3-You're able to find the transition between states. As they're the Recursive calls

Means $$$dp[i][tg][tp] = dp[i+1][tg - gp[i]][tp + pf[i]] + dp[i+1][tg][tp]$$$

Sometimes those are enough to write an iterative solution, sometimes not. You just need to practice understanding what does the dp array mean, like what does dp[i][tg][tp] means here, Once you're able to grasp the physical meaning of a dp state, You're probably able to discover the transitions and the base cases without writing recursive solutions.

Wow I never realized this I guess im getting confused because of order or something. Thank you so much for the help :)

I guess you can(in some cases) store all the states(push_back them to an array when the dfs $$$ends$$$, and mark each state using boolean array or a bitset), so? i don't think if it helps with memory, but is indeed an iterative way to think about it :).

Well I tried once but it was just messy. Atleast I couldnt code it properly. I wanna learn that table method. Lets see. Thanks for the help!

Implementation using arraysImplementation using mapWill ponder over and try to understand this thank you :)

one thing you could do is maintain vector or stack, maintaining some struct binding of required variables, and visited branch, for example if you have gone through the child of particular parent, you should maintain a pointer pointing which child had already been visited, so you could directly start from that. this method is not that memory efficient but still very faster, as you are avoiding system stack which was used by recursion.

Still that would be bad right?

code for iterative postorder traversal of binary treeThis is my code for iterative postorder traversal of binary traversal it is 100 percent faster than other submissions also 100 percent memory efficient in leetcode. When I am free I will post the iterative version of your dp.

Thank you for your time :)

Often you can sort by dfs order then just do iterative dp from there. Still requires a dfs though.

What does sorting by dfs order mean? Thank you

I think that means pushing back values by entry time or exit time.