dynamic programming - ghdrako/doc_snipets GitHub Wiki

Memoization

def fibonacci(n, memo={}):
  if n <= 1:
    return n
  if n not in memo:
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
  return memo[n]

Tabulation

Tabulation, also known as bottom-up dynamic programming, involves solving the subproblems in a specific order and using a table or array to store the results of each subproblem. The table is filled iteratively, starting from the base cases and progressing towards the final solution. By computing the subproblems in a specific order, we can ensure that the results of the dependent subproblems are already available when needed.