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

Dynamic Programming Memoization vs Tabulation
Автор Bakry, история, 7 лет назад, По-английски

Hello ,

I saw most of programmers in Codeforces use Tabulation more than Memoization So , Why most of competitive programmers use Tabulation instead of memoization ?

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
7 лет назад, # |
← Rev. 4   Проголосовать: нравится +12 Проголосовать: не нравится

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!

→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

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

    Thanks :).......Do you have resources to learn DP in Tabulation I am good in it in Memoization

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

      Do easy problems with memoization and then convert it.

      E.g http://www.usaco.org/index.php?page=viewproblem2&cpid=574

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

        I don't Know tabulation...I know memoization only :( Do you have resources to learn tabulation ?

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

          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-дерево

          As for resources geeksforgeeks is fine, but you can usually understand after reading things from 3-5 sources.

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

            Thanks :).....I will try to learn tabulation and solve those problems

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

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 - Генерация строки

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

→ Ответить