Dynamic Programming Introduction

Dynamic Programming solves complex problems by breaking them into overlapping subproblems and storing results.

Two Approaches

• Top-Down — Memoization (recursive + cache)
• Bottom-Up — Tabulation (iterative + table)

Syntax

COMPUTER-SCIENCE

1
2
3
4
5
6
7
8
9
10
11
12

# Fibonacci — Naive O(2^n)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

# Fibonacci — DP O(n)
def fib_dp(n):
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Fibonacci with Memoization

PYTHON

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Naive recursion O(2^n)
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

# With memoization O(n)
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

print(f"fib(10) = {fib_memo(10)}")
print(f"fib(30) = {fib_memo(30)}")

Try It Yourself

Practice

1

Exercise

When should you use dynamic programming?

Answer

When the problem has overlapping subproblems and optimal substructure.

Quick Quiz

1

What is memoization?

Sorting data

Caching recursive results

Deleting data

Encrypting data

Memoization stores results of expensive function calls to avoid recomputation.

Retry Quiz

Interview Questions

What is the difference between memoization and tabulation?

Memoization is top-down (recursive + cache). Tabulation is bottom-up (iterative + table). Tabulation is often more space-efficient.

Tutorial Complete

Back to Computer Science