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

Автор Bakry, история, 9 лет назад, По-английски

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

»
9 лет назад, скрыть # |
← 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!

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 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 - 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).