### I_m_sfg's blog

By I_m_sfg, history, 5 weeks ago,

Greetings to everyone, I am struggling with tabulation dp. I am solving the DP question by memorizing, but not all questions should be solved by memorizing, and memorizing adds an extra O(n) space. Please give me some resources and questions where I can learn tabular DP.

• +11

 » 5 weeks ago, # |   0 who said 'not all questions should be solved by memorizing'? I see ashishgup , he always use memo
•  » » 5 weeks ago, # ^ |   0 lot of questions... example:-https://leetcode.com/problems/find-all-possible-stable-binary-arrays-ii/description/
•  » » » 5 weeks ago, # ^ |   +1 umm there is actually nothing to study for tabular ... you should first do memoization if that works well and good,if it gives TLE just convert your code to tabular if this gives MLE and you see there are i-1,i-2 type of states go for space optimized ...if its 2D you may go for knapsack optimization... i prefer simple procedure write brute force recursion -> memoize it -> tabularize it -> space optimized it -> knapsack optimize it ....if still gives tle then you have to come up with better algorithm or kick off dimensions by some observations rest is up to you
•  » » » 4 weeks ago, # ^ |   +8 Of course it can be solved with memoizing... Codeclass Solution { vector>> memo; vector>> has_memo; Modint dp (int zero, int one, int last, int limit) { if (has_memo[zero][one][last]) return memo[zero][one][last]; if (zero + one == 0) return Modint(0); if (zero + one == 1) { if (zero == 1 && last == 0) return Modint(1); if (one == 1 && last == 1) return Modint(1); return Modint(0); } Modint ans (0); if (last == 0) { if (zero > 0) ans += dp(zero - 1, one, 0, limit) + dp(zero - 1, one, 1, limit); if (zero >= limit) if (zero == limit && one == 0) ans -= Modint(1); else ans -= dp(zero - limit, one, 1, limit); } if (last == 1) { if (one > 0) ans += dp(zero, one - 1, 0, limit) + dp(zero, one - 1, 1, limit); if (one >= limit) if (one == limit && zero == 0) ans -= Modint(1); else ans -= dp(zero, one - limit, 0, limit); } has_memo[zero][one][last] = 1; memo[zero][one][last] = ans; return ans; } public: int numberOfStableArrays (int zero, int one, int limit) { limit++; memo = vector>> (zero + 1, vector> (one + 1, vector (2))); has_memo = vector>> (zero + 1, vector> (one + 1, vector (2, 0))); Modint ans = dp(zero, one, 0, limit) + dp(zero, one, 1, limit); return (int) ans.val; } }; There are some problems where memoizing is not very good. Specifically, there are kinda 2 types of DP problems: ones where it is easier to think in terms of how $\mathrm{dp}[state]$ is calculated based on previous states; ones where it is easier to think in terms of how $\mathrm{dp}[state]$ affects future states. Memoizing might not be very helpful for the second type, that's true. This problem, at least the solution above, is very much in the first type, however.
 » 4 weeks ago, # | ← Rev. 2 →   +6 Flow of For loops is the main struggle people in Tabular DP Best way is to write the state clearly and seeing the blocks you need to fill first in order to get your current state hence deciding the dirn of each variable in for loop
 » 4 weeks ago, # | ← Rev. 2 →   0 I think that a lot of tabular DP solutions require you to have good working memory. If you don't naturally have good working memory, you might not ever be able to write $\ge 3D$ tabular DP solutions.
•  » » 4 weeks ago, # ^ |   +1 :facepalm: you know paper exists right? You don't have to keep information about all the states in your head, which isn't even so hard to do btw.
•  » » » 4 weeks ago, # ^ |   -8 Having pen and paper but poor working memory is like having a map of the city you're in but not knowing where you are on that map. What good is the map when you can't use it to make your way forward?
•  » » » » 4 weeks ago, # ^ |   0 I don't even understand this analogy. Anyway, there is nothing difficult in writing tabular DP, especially when you can already write a memo solution. You already have the transitions and know what you need to memoize. Just maybe a bit more practice with tabular DP. It's weird how you try to attribute everything to cognitive abilities.
•  » » 4 weeks ago, # ^ |   -6 How to be expert
•  » » 4 weeks ago, # ^ |   0 $\ge3D$ tabular DP often does not require any visualization and often makes thinking harder. In any dp, with a transition $from \rightarrow to$ we just need to make sure state $from$ is computed before state $to$. For example:$dp[i + 1][j - 1][2k] \rightarrow dp[i][j][k]$When we iterate, we go in decreasing $i$ since $i + 1 > i$, increasing $j$ since $j - 1 < j$, and decreasing $k$ since $2k > k$. The dimensions are independent, which makes this work. Almost all DPs I have done can be thought of in a similar way.
•  » » 4 weeks ago, # ^ |   0 DP should not be visualized/memorized. You should understand what each state means and how it can be used to compute other states. It shouldn't need memory.
 » 4 weeks ago, # |   0 They are the same thing.