An Introduction to Dynamic Programming

By Riolku
Written 12 days ago

Dynamic programming is almost the same as recursion; we have a problem that can be solved by sub-problems, with some sort of base case. We have talked about recursion with memoization in another lesson, here we discuss an alternate form that is iterative.

We can think of recursion as a top-down structure. In contrast, dynamic programming is bottom-up.

Let's come back to the Fibonacci function. What if we store our results in an array and iterate up?

def f(n):
  dp = [1, 1]
  # compute the new answers
  for i in range(2, n + 1):
    dp.append(dp[i - 1] + dp[i - 2])

  return dp[n]

If we now try f(100), we see that it finishes right away, as we hoped. This is a good example of iterative dp. We can almost always use this to replace memoized recursion. One example of when we cannot do this as easily is if we cannot iterate through all the states, such as if they are not sequential.