I_m_sfg's blog

Struggling with tabulation dp
By I_m_sfg, history, 6 months ago, In English

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.

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

who said 'not all questions should be solved by memorizing'? I see ashishgup , he always use memo

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lot of questions... example:-https://leetcode.com/problems/find-all-possible-stable-binary-arrays-ii/description/

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Of course it can be solved with memoizing...

      Code

      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.

      → Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    How to be expert

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$\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.

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

They are the same thing.

→ Reply