Intuition The ONE core ideaDynamic Programming means solving a big problem by first solving the smaller copies of itself
hidden inside it , then writing each small answer down once so you never recompute it. Everything
in the parent note — Fibonacci, coin change, knapsack — is just this one trick wearing different
clothes.
Before you can read the parent note, you need to own every symbol it throws at you. Below, each
tool is built from nothing: plain words first, then a picture, then the reason the topic can't live
without it. Read top to bottom — each item leans on the one above it.
Definition A function as a machineWhen we write F ( n ) F of n ". Here F name of a machine ,
and n input you feed it . The machine hands back one number, its output .
Example: F ( 5 ) F
WHY the topic needs this: every DP object — F ( n ) dp [ a ] dp [ i ] [ w ] F ( n )
Intuition Subscripts vs brackets are the same ideaw i weights [ i ] same thing : "the i one slot in a row of
numbers .
An index is a counting label — 0 , 1 , 2 , 3 , … which position you mean in a
line of things. We use letters like n i a w stand-ins for some whole
number we haven't fixed yet.
A sequence is just a row of numbers, one per index. Fibonacci is a sequence: position 0 0 1 1 2 1
n ≥ 2 n is at least 2 " — the symbol ≥ greater than or equal to .c ≤ a c is at most a " — ≤ less than or equal to .
WHY the topic needs this: the whole game is "answer at position n
An array (Python calls it a list) is a row of numbered boxes. dp = [0,1,1,2,3,5] is six
boxes; dp[3] grabs the box at index 3 2 Counting starts at 0 , so dp[0]
is the first box.
dp is where we write each small answer once and keep it . This written-down memory is the
literal difference between DP and plain recursion. dp[a] = "the answer for target a dp[i][w] = "the answer using the first i w
dp[i][w] has TWO brackets
One bracket is a single row. Two brackets is a grid — rows and columns. In knapsack the row
i w
WHY the topic needs this: "store the answer and reuse it" is meaningless without a place to
store it. The array is the memory in "recursion + memory."
Recursion is when a machine's instructions include "…and to finish, run me again on a
smaller input." F ( n ) = F ( n − 1 ) + F ( n − 2 ) F Recursion and Memoization for the deep dive.
A base case is the input so small the machine answers directly , without calling itself.
F ( 0 ) = 0 F ( 1 ) = 1 dp[0]=1 (coin
count) and dp[0]=0 (min coins) are base cases too.
Common mistake Recursion with no base caseWhy it feels fine: the rule "call myself on something smaller" seems complete.
Why it's wrong: without a floor the calls shrink forever (n , n − 1 , n − 2 , … Fix: always define the smallest inputs by hand first.
WHY the topic needs this: "break a problem into smaller versions of itself " is recursion.
DP is recursion that remembers.
Memoization = recursion + a notepad. Before computing an answer, check the notepad
(if n in memo). If it's there, reuse it. If not, compute it and write it down . The word comes
from "memo," a note-to-self. Compare with tabulation in
Tabulation vs Memoization .
Intuition Why the notepad turns exponential into linearWithout memory, machine F F ( 3 ) F ( 0 ) , F ( 1 ) , … , F ( n ) exactly once — that's n + 1 linear , instead of ≈ ϕ n Time and Space Complexity .
WHY the topic needs this: "solve each small version once, store, reuse" is the definition of
memoization — the second half of "DP = recursion + memory."
ϕ ϕ ϕ ≈ 1.618 multiply by ϕ each level, so n ≈ ϕ n
Θ ( ⋅ ) Θ ( n ) theta of n " means "the amount of work grows in step with n n Θ ( ϕ n ) multiplies every time n Time and Space Complexity .
ϕ n ϕ n ϕ n ϕ 3 = ϕ ⋅ ϕ ⋅ ϕ n exponent — a count of repeated multiplications.
WHY the topic needs this: these symbols are how the parent measures whether DP paid off.
Θ ( ϕ n ) → Θ ( n )
∞ float('inf'). We seed unreachable amounts with ∞ real
answer is automatically smaller and wins the min
min max min ( a , b ) smaller of two numbers; max ( a , b ) larger . min c ≤ a c fewest
coins (min most value (max
+= operator
dp[a] += dp[a-c] is shorthand for dp[a] = dp[a] + dp[a-c] — "add this onto what's already
there. " Coin-count accumulates ways, so it adds rather than replaces.
WHY the topic needs this: every recurrence in the parent is a min max + =
A subset is any selection of items — take some, leave the rest. From { A , B , C } { } { A } { A , C } { A , B , C }
0/1 knapsack means each item is taken 0 times or 1 time — a yes/no switch, never twice.
Contrast with unbounded , where an item may be reused freely (see
Unbounded Knapsack and Rod Cutting ). This 0-or-1 choice is why knapsack references the
previous row dp[i-1]. The subset flavour also drives
Subset Sum and Partition Problems .
WHY the topic needs this: "pick a subset maximizing value" is the knapsack statement, and the
0/1 constraint is the single detail that makes it not the same as coin change.
Definition Optimal substructureThe best answer to the whole is built from best answers to its parts. If the best way to make
amount 6 ends in a coin 3, then the remaining amount 3 must also be solved best.
Definition Overlapping subproblemsThe same small problem shows up again and again (like F ( 3 )
Intuition Both must hold — else you don't need DPNo overlap ⇒ nothing to reuse ⇒ plain divide-and-conquer suffices. No optimal substructure ⇒ you
can't build big answers from small ones ⇒ DP's recurrence is invalid. DP lives exactly where
both are true. (This is also the fence-line with Greedy Algorithms , which commits to a
local best without checking every combination.)
What does F ( n ) Feed input n F
Where does array counting start? At index 0 dp[0] is the first box.
What are the two brackets in dp[i][w]? A grid: row i w
What is recursion in one sentence? A machine whose instructions tell it to run itself on a smaller input.
What is a base case and why must it exist? The smallest input answered directly; without it recursion never stops.
What does memoization add to recursion? A notepad — compute each distinct answer once, store it, reuse it.
Why does memoized Fibonacci run in Θ ( n ) Θ ( ϕ n ) Each of the n + 1
What does ≥ ≤ ≥ ≤
Why seed unreachable amounts with ∞ So any real answer is automatically smaller and wins the min
Why is dp[0]=1 for coin-count but dp[0]=0 for min-coins? One way to make 0 (pick nothing) vs zero coins needed to make 0.
What does "0/1" mean in 0/1 knapsack? Each item is taken zero or one time — never reused.
What two conditions must hold for DP to apply? Optimal substructure AND overlapping subproblems.
