Dynamic programming

26 Jun 2022 in Study / Computer science on Dynamic programming

Algorithms

calculated results → memory

Condition

1. small parts x n → Big problems solving
2. identical small problems solving : repeat

Method

• Top-down

  • completely calculated one is stored in memory → calling it when it needs to be used as big problem is disassociated small problems

  • mainly use recursion

  • recursion’s problem : unnecessary repeating calculation → solving by Top-down
    ex) fibonacci

  

• Bottom up (mainly use)
  • solving a small problem and stored in memory → using for solving a next problem
  • mainly use loop

DP table

calculated result will be stored in DP table

• Top-down (fibonacci)

dp = [0] * 1000
def fibonacci(x):
  if x == 1 or x == 2:
    return 1
  if dp[x] != 0:
    return dp[x]
  dp[x] = fibonacci(x - 1) + fibonacci(x - 2)
  return dp[x]

• Bottom up (fibonacci)

dp = [0] * 100
dp[1] = 1
dp[2] = 1

for i in range(3, 100):
  dp[i] = dp[i - 1] + dp[i - 2]