Hello ,
I saw most of programmers in Codeforces use Tabulation more than Memoization So , Why most of competitive programmers use Tabulation instead of memoization ?
Hello ,
I saw most of programmers in Codeforces use Tabulation more than Memoization So , Why most of competitive programmers use Tabulation instead of memoization ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
Its a matter of convenience/taste in most cases. Though, there are a few advantages of Tabulation:
1) You can reduce space complexity, if while updating dp states you only need values of only few other dp states. E.g : Knapsack . Therefore in some problems it becomes impossible to solve a dp problem using memoization because of memory constraints.
2) Let's say dp[i][j] is summation of dp[i - 2][k], k ranging from min to max. Then again in this case, tabulation is the only option, as you can tabulate dp[i - 2] and construct its prefix sum. However, in memoization you won't be able to do this.
On the other hand, recursion with memoization goes only to the required states and might be a bit faster in some cases!
In memoization you can create prefix sums.
An example from the recent contest: 33823272
Clarification: dps stores prefix sums while dp stores normal values
Downvotes because correct? Sad.
Thanks :).......Do you have resources to learn DP in Tabulation I am good in it in Memoization
Do easy problems with memoization and then convert it.
E.g http://www.usaco.org/index.php?page=viewproblem2&cpid=574
I don't Know tabulation...I know memoization only :( Do you have resources to learn tabulation ?
Solve some easy/classical problems with iteration first:
0-1 Knapsack (with space reduction)
Coin Problem (space reduction)
Many problems are variants of these, you can find them in the codeforces problemset.
Now try to solve this, both with recursive and iterative: 431C - k-Tree
As for resources geeksforgeeks is fine, but you can usually understand after reading things from 3-5 sources.
Thanks :).....I will try to learn tabulation and solve those problems
I default to recursion unless the iterative method is necessary/more obvious.
Recursion will give you segfault or some other weird error if you recurse too deep. (Usually > 1e5, but someone might find counterexample)
Example problem: 710E - Generate a String
My recursive solution — gets RTE (segfault) My iterative solution — gets AC
Personally it's easier for me to convert recursion to iterative than to write out iterative in the first place, unless it's a variant of some classical problem that I know (e.g knapsack).
Thanks :)