Lesson 1-3 Notes

Core Idea

Dynamic Programming (DP) is a technique for solving problems that contain:

1. Overlapping subproblems
2. Optimal substructure

The main goal is:

Solve each subproblem once and reuse the result.

---

DP Workflow

For every DP problem, identify:

State

What information uniquely identifies a subproblem?

Examples:

fib(n)
stairs(n)
dp[i]
dp[i][w]

Transition

How is the current state derived from smaller states?

Base Case

What are the smallest known answers?

Answer

Which state contains the final answer?

---

Fibonacci

State:

fib(n)

Transition:

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

Base Cases:

fib(0) = 0
fib(1) = 1

Observation:

fib(3)
fib(2)

are recomputed many times.

Memoization avoids repeated computation.

---

Climbing Stairs

Allowed moves:

1 step
2 steps

State:

stairs(n)
=
number of ways to reach stair n

Transition:

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

Base Cases:

stairs(0) = 1
stairs(1) = 1

Important idea:

stairs(0) = 1

represents the empty solution (“do nothing”).

---

Generalization

Allowed moves:

{1,3,5}

Transition:

stairs(n)
=
stairs(n-1)
+
stairs(n-3)
+
stairs(n-5)

Useful convention:

stairs(n < 0) = 0
stairs(0) = 1

Invalid states contribute zero.

---

House Robber

Problem:

Cannot rob adjacent houses.

State:

dp[i]
=
maximum money obtainable
from houses [0..i]

Transition:

dp[i]
=
max(
    dp[i-1],
    dp[i-2] + value[i]
)

Meaning:

Option 1:
Do not rob house i
 
Option 2:
Rob house i

Important insight:

dp[i]

does not mean:

money in house i

It means:

best answer considering houses [0..i]

---

Min Cost Climbing Stairs

Backward State:

dp[i]
=
minimum cost to arrive at stair i

Transition:

dp[i]
=
cost[i]
+
min(
    dp[i-1],
    dp[i-2]
)

Alternative Forward State:

f[i]
=
minimum cost from stair i to TOP

Transition:

f[i]
=
cost[i]
+
min(
    f[i+1],
    f[i+2]
)

Observation:

A DP problem may have multiple valid state definitions.

---

0/1 Knapsack

Problem:

Each item can be taken at most once.

State:

dp[i][w]
=
maximum value achievable
using items [0..i]
with capacity w

Why 2D?

Because:

dp[i]

alone does not tell us:

remaining capacity

Capacity is part of the state.

---

Decision

For item i:

Take item i
or
Do not take item i

Transition:

If item fits:

dp[i][w]
=
max(
    dp[i-1][w],
    dp[i-1][w-weight[i]] + value[i]
)

Otherwise:

dp[i][w]
=
dp[i-1][w]

---

Recursive View

Knapsack can be written recursively:

knapsack(i, c)

where:

i = current item
c = remaining capacity

Decision:

skip item i
take item i

Observation:

knapsack(i, c)

and

dp[i][c]

represent the same state.

A DP table is often just cached recursion.

---

1D Optimization

Since:

dp[i][w]

depends only on:

dp[i-1][...]

the table can be compressed to:

dp[w]

For 0/1 Knapsack:

for (c = W; c >= weight[i]; --c)

Capacity must be processed backwards.

Reason:

Forward iteration may accidentally reuse the same item multiple times.

---

Lessons Learned

DP is not an array

The array is only storage.

The important parts are:

State
Transition
Base Case

Always remember what the state means

Most mistakes happen when the meaning of the state is forgotten.

Recursive thinking is often the easiest way to derive DP

Process:

Recursion
→ Memoization
→ Bottom-up DP
→ Space Optimization

State Compression

DP often works by:

Large amount of history
→ compressed into a small state

Examples:

fib(n)
 
dp[i]
 
dp[i][w]