Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

retr0coderxyz's blog

By retr0coderxyz, history, 5 weeks ago, In English,

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

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by retr0coderxyz (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by retr0coderxyz (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

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

dp[i][tg][tp]=(solve(i+1,tg-gp[i],tp+pf[i])+solve(i+1,tg,tp))%MOD;

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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!

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Implementation using arrays
      Implementation using map
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Still that would be bad right?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      code for iterative postorder traversal of binary tree

      This 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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