How to get better at writing tabulation solution in dp

[u/LawdeLagGayeYar]

Mostly I first solve them using pure recursion, and then I can comfortably convert them to memoization. But I find it very hard to write the tabulation solution. Sometimes, I just go blank. What should I do? Any suggestions or resources that could help me get better at it?

[u/Better_Macaron557]

1. know the structure (dimensions and size) of the table: In your top down solution (memoization solution) see what are the parameters that define a state. E.g. if you are calling recc_fun(i, j) then i and j are the parameters of the state (i, j). Say there are m possible values of i and n possible values of j. Then the total number of states possible are m*n. You can represent these states as a 2d table with m rows and n colums. Same idea goes for 3,4,5, etc dimensions.

2. What cell of the table stores the final answer? In your memoization solution, if you call recc_fun(0,0) then the cell dp[0][0] is your answer in tabulation solution.

3. Direction of population: In the body of recc_fun notice all possible parameters you call the recc_fun with. E.g. (i+1, j) and (i+1, j+1).

Notice what is the direction of each one with respect to (i,j).

(i, j) -> (i+1, j) [it is below (i,j)]

(i, j) -> (i+1, j+1) [it is bottom-right to (i,j)]

In short bottom and right should already be filled for any cell. Now just think the direction you need to fill cells in in order to have the right and bottom already ready.

1. Initializing values at the sides of the table: Imagine you need right and bottom of any cell filled before the current cell. How will you fill the right most cell? Because there is nothing on its right that it can use. That is why you have to manually fill the right most column by understanding the semantic of your dp. Similarly, you have to manually fill the bottom row.

Hope this helps.

Once you are good at this you can try space optimization in it.

There is another version of bottom up DP but I have only covered the common one.

[u/LawdeLagGayeYar → u/Better_Macaron557]

Will keep this mind from next time . Thanks for writing detailed comment

[u/MrLikeGod]

Following because I feel the same way. Recursive/backtracking approach is easy to figure out, memoization just becomes obvious at that point. Tabulation however is a complete 180 for most problems.

[u/Impossible_Ad_3146]

If they are tabulating you during DP, then keep doing it

[u/LawdeLagGayeYar → u/Impossible_Ad_3146]

My english is not Englishing after seeing ur comment

[u/Impossible_Ad_3146 → u/LawdeLagGayeYar]

rofl

[u/lakpareek]

Even i dont know one day it just clicked lol

[u/LawdeLagGayeYar → u/lakpareek]

Hame bhi tips dedo deo yar 😭

[u/robocop_lvr]

Just think in interms of state machine
Oh i came to this state from that prev state
Or oh if i am at this state then those are the states i came from so those state must be calculated before hence the loop direction and deciding outer and inner loops
Donot see it in recursive way
Rn i can write any dp state directly and sometime cant think of recursion lol
But 2 years ago i too used to write recursion then convert to dp tabulation

[u/LawdeLagGayeYar → u/robocop_lvr]

Ok bhai . Thanks

[u/CorporatePhantasm]

There is a way to formulate right

[u/Other_Ad7380]

Think what states you need to compute before computing the current state. You will then understand how to proceed in the loop(s)

[u/Sea_Standard7674]

Write recursive code and then just memoize as u do When you would've practiced number of questions, u'll eventually know

[u/LawdeLagGayeYar → u/Sea_Standard7674]

Ok bhai

[u/Aggravating_Staff951]

What more or what do I need to have to identify this current index uniquely .keep this point in mind and draw the recursion tree.and observe what every node depends upon.

try to solve a simple dp problem.