Dynamic Programming

algorithms

Definition

Dynamic Programming

Dynamic programming is an approach to solve complex problems by reusing partial problems to solve the next bigger problem until the total problem is solved.

Examples

Fibonacci

It makes sense to solve Fibonacci numbers with dynamic programming since there are overlapping sub-problems. Computing Fibonacci numbers is a recursive problem.

def fib(n: int) -> int:
    dp: list[int] = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])
    return dp[n]

Of course, dp doesn’t have to always be a list. It can be a dict or map or any other $O(1)$ access data structure.

Knapsack Problem

Another classic DP-problem is the Knapsack Problem. Greedy algorithms don’t work here and all top-down approaches are comparatively slow.