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.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3845 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3630 |
| 4 | orzdevinwang | 3573 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | jqdai0815 | 3532 |
| 8 | ecnerwala | 3501 |
| 9 | gyh20 | 3447 |
| 10 | Rebelz | 3409 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | adamant | 163 |
| 2 | awoo | 163 |
| 4 | TheScrasse | 154 |
| 5 | nor | 153 |
| 6 | maroonrk | 152 |
| 6 | -is-this-fft- | 152 |
| 8 | Petr | 145 |
| 9 | pajenegod | 144 |
| 9 | orz | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.06.2024 18:02:20 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
who said 'not all questions should be solved by memorizing'? I see ashishgup , he always use memo
lot of questions... example:-https://leetcode.com/problems/find-all-possible-stable-binary-arrays-ii/description/
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
Of course it can be solved with memoizing...
There are some problems where memoizing is not very good. Specifically, there are kinda 2 types of DP problems:
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.
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
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.
: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.
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?
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.
How to be expert
$$$\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.
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.
They are the same thing.