Intermediate Module

Dynamic Programming

Unlock the power of optimal substructure: learn to recognize and solve problems by breaking them into overlapping subproblems.

Back

12 hours

4 key concepts

What is Dynamic Programming?

Dynamic Programming (DP) is a technique for solving problems by breaking them into overlapping subproblems and storing their solutions to avoid redundant computation. It works when a problem has:

Optimal Substructure

The optimal solution to the problem can be constructed from optimal solutions of its subproblems.

Overlapping Subproblems

The same subproblems are solved multiple times. DP stores solutions to avoid recomputation.

Fibonacci: A Classic Example

Interactive

Compare three approaches to computing Fibonacci numbers: naive recursion, memoization (top-down DP), and tabulation (bottom-up DP).

Naive Recursion

O(2^n)

Directly follows the mathematical definition. Extremely slow due to repeated calculations of the same values.

n =

Speed:

Click "Compute" to start

Function Calls / Steps

F(8)

The 5-Step DP Approach

Define the State

What does dp[i] or dp[i][j] represent? This is the most critical step.

For Fibonacci: dp[i] = the ith Fibonacci number

Find the Recurrence Relation

How can you express dp[i] in terms of smaller subproblems?

dp[i] = dp[i-1] + dp[i-2]

Identify Base Cases

What are the simplest subproblems you can solve directly?

dp[0] = 0, dp[1] = 1

Determine Computation Order

In what order should you fill the table so dependencies are satisfied?

Compute dp[2], then dp[3], ..., up to dp[n]

Extract the Answer

Which entry in the table contains the final answer?

Return dp[n]

Classic DP Problems

Fibonacci Sequence

O(2^n) O(n)

Find the nth Fibonacci number

F(n) = F(n-1) + F(n-2)

Longest Common Subsequence

O(2^(n+m)) O(nm)

Find longest subsequence common to two sequences

LCS[i][j] = LCS[i-1][j-1]+1 if match, else max(LCS[i-1][j], LCS[i][j-1])

0/1 Knapsack

O(2^n) O(nW)

Maximize value while respecting weight limit

K[i][w] = max(K[i-1][w], v[i] + K[i-1][w-w[i]])

Edit Distance

O(3^n) O(nm)

Minimum edits to transform one string to another

D[i][j] = min(D[i-1][j]+1, D[i][j-1]+1, D[i-1][j-1]+cost)

Coin Change

O(S^n) O(nS)

Minimum coins to make a sum

dp[i] = min(dp[i], dp[i-coin]+1) for each coin

Longest Increasing Subsequence

O(2^n) O(n log n)

Find longest strictly increasing subsequence

LIS[i] = max(LIS[j]+1) for all j < i where a[j] < a[i]

DP in the AI Coding Era

Recognize DP Problems

When asking AI to solve optimization problems, knowing if DP applies helps you evaluate the solution quality. AI might give a brute-force solution when DP exists.

Guide the Solution

"Use dynamic programming with state dp[i][j] representing..." leads to better AI-generated code than "solve this optimization problem."

Keep Learning

Explore more modules to complete your algorithmic foundation.