Блог пользователя I_m_sfg

Struggling with tabulation dp
Автор I_m_sfg, история, 6 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится +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

      → Ответить
    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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.

      → Ответить
»
6 месяцев назад, # |
← 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

→ Ответить
»
6 месяцев назад, # |
← 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.

→ Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится +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.

    → Ответить
    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится -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?

      → Ответить
      • »
        »
        »
        »
        6 месяцев назад, # ^ |
          Проголосовать: нравится 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.

        → Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    How to be expert

    → Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 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.

    → Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 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.

    → Ответить
»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

They are the same thing.

→ Ответить