Bakry's blog

Dynamic Programming Memoization vs Tabulation
By Bakry, history, 7 years ago, In English

Hello ,

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

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

»
7 years ago, # |
← Rev. 4   Vote: I like it +12 Vote: I do not like it

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!

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

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

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

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

      Do easy problems with memoization and then convert it.

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

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

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

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

          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.

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

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

            → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply