Intuition The ONE core ideaA hard problem is often just a small problem asked over and over — Dynamic Programming means solve each small problem once, write the answer on a sticky note, and reuse it forever . Everything on this page exists to earn the symbols and pictures you need before that idea makes full sense.
This page assumes you have seen nothing . Before you can read the parent note Dynamic Programming , you must be fluent in the tiny alphabet below. We build each symbol on the one before it.
Every symbol here orbits one word: subproblem .
A smaller copy of the original problem . If the big task is "compute F ( 5 ) F ( 3 )
Picture it as a nesting doll : the big doll (whole problem) contains smaller identical dolls (subproblems) inside it. You cannot understand DP until you see problems this way.
Why the topic needs it: every other symbol below is a way of naming , counting , or storing subproblems. No subproblem, no DP.
F ( n ) n F name for a machine . You feed it a number n F ( 5 ) 5
Picture a vending machine : press button n
The letter F K fib
The thing in the brackets, n input — the size or state of the problem.
F 0 , 1 , 2 , 3 , … n ∈ N 0 N 0 including zero." So valid inputs are n ∈ { 0 , 1 , 2 , … }
Intuition Why we write it this wayBecause a subproblem is "the same machine on a smaller input", the notation F ( n − 1 ) means "the subproblem one size smaller." The symbol is chosen precisely so that shrinking the input = shrinking the problem. Since n ∈ N 0 F ( 0 ) , F ( 1 )
An equation where F ( n ) F n ≥ 2 F ( n ) = F ( n − 1 ) + F ( n − 2 ) n n − 1 n − 2
Why a "+ literally the sum of two smaller answers. Different problems combine differently (we will see max
The smallest input where you already know the answer without shrinking further . For Fibonacci: F ( 0 ) = 0 F ( 1 ) = 1 n ∈ N 0 0 1 F ( − 1 )
Picture recursion as a tree that grows downward : one call at the top splits into smaller calls, which split again, until every branch hits a base case (a leaf).
Common mistake "Recursion and DP are the same thing."Why it feels right: DP is built on recursion, so they look identical on paper. The fix: recursion is only the machine ; DP adds a memory so the machine never re-does a call. See §5. Full detail lives in Recursion .
Look again at the tree figure (s02). Find every node labelled F ( 3 ) F ( 5 ) F ( 3 ) twice , F ( 2 ) three times . Those repeats are the whole reason DP exists.
Definition Overlapping subproblems (the picture)When the same node label shows up in more than one place in the recursion tree. Visually: identical dolls appearing again and again.
Definition Distinct subproblemsHow many different node labels exist, ignoring repeats. In F ( 5 ) F ( 0 ) , F ( 1 ) , F ( 2 ) , F ( 3 ) , F ( 4 ) , F ( 5 ) 6 , i.e. n + 1 many nodes (its size grows exponentially — see §4), only n + 1
This gap — many nodes, few distinct — is the exploitable waste. Detailed tree-counting lives in Recursion Trees .
Why the topic needs it: DP's whole payoff is "solve the few distinct ones, skip all the repeats." You cannot see the payoff without seeing the repeats.
O ( g ( n )) g g ( n ) simple yardstick function (like n n 2 2 n O ( g ( n )) n below some fixed multiple of g ( n ) g n O ( 2 n ) O ( n )
Picture two runners:
O ( n ) ramp .exponential growth shoots up a near-vertical cliff .
Intuition Why exponential is a catastrophe — and the true branching factorEach node in the Fibonacci tree spawns (up to) two children, so the tree roughly doubles each level. But the two branches are uneven (F ( n − 1 ) F ( n − 2 ) Θ ( φ n ) φ = 2 1 + 5 ≈ 1.618 not quite 2 n paradigm is that it turns that cliff into a ramp: exponential → O ( n ) Θ exactly like", a tight version of O Time Complexity Analysis .
Definition Table (the DP store)A ==list or grid where slot i i d p [ i ] i
Two symbols to read comfortably:
d p [ i ] 1-D row of sticky notes (Fibonacci uses this).d p [ i ] [ c ] 2-D grid, one axis per input. Knapsack uses i c
Picture d p [ i ] [ c ] spreadsheet : rows are items, columns are capacities, each cell is one stored answer.
Why the topic needs it: the table is the memory that upgrades plain recursion into DP. Without it, §3's repeats are recomputed; with it, each distinct doll is solved once.
max ( a , b ) a b
Before the recurrence, meet its symbols. In the Knapsack Problem we have a list of items; item number i
v i value of item i w i weight of item i c capacity remaining in the backpack right now.
K ( i , c ) K ( i , c ) answer-machine name (just like F "the best total value achievable using only items 1 i c Inputs are whole numbers: i ∈ { 0 , 1 , … , n } c ∈ { 0 , 1 , … , W }
Definition Optimal substructure (plain words)The best answer to the whole is built out of best answers to its parts . Above, the best packing of items 1.. i 1.. i − 1
max + adds because the whole is a sum. Knapsack chooses the best option, so it uses max The combining operator is dictated by what the problem asks — sum, max, min, count. Always ask "what is this problem combining?" before writing the recurrence.
Contrast with Greedy Algorithms (which grabs the locally best option once and never reconsiders) and Divide and Conquer (whose subproblems are all distinct , so no sticky notes help). Other classic optimal-substructure problems: Longest Common Subsequence , Bellman-Ford .
Subproblem = smaller copy
Domain n in naturals with zero
Recurrence F calls smaller F
Base case stops recursion
Overlapping vs distinct subproblems
Table stores each answer once
max and optimal substructure
Every arrow means "you need the left box before the right box makes sense." The topic sits at the bottom because it fuses all these foundations.
Cover the right side and answer out loud before opening the parent note.
What does F ( n ) The answer to the problem when the input has size/value n n
What is the domain of Fibonacci's F The non-negative integers n ∈ N 0 = { 0 , 1 , 2 , … }
What is a subproblem? A smaller copy of the same problem (a smaller nesting doll).
What is a base case and why is it required? The smallest input whose answer you know directly; without it the recursion never stops (and it keeps n
In a recursion tree, what does "overlapping subproblems" look like? The same node label appearing in more than one place in the tree.
Distinct subproblems for F ( 5 ) Only n + 1 = 6 Θ ( φ n ) ≈ 1.61 8 n
What does O ( g ( n )) The running time stays below a fixed multiple of the yardstick function g ( n ) n g
What is d p [ i ] [ c ] A cell in a 2-D table storing the answer to the subproblem indexed by i c
Memoization vs tabulation in one line each? Memoization = top-down recursion that checks the table first (lazy); tabulation = bottom-up loop filling smallest first (eager).
What does max ( a , b ) Returns the larger of a b
What are v i w i c K ( i , c ) v i i w i c K ( i , c ) 1.. i c
Why does the knapsack recurrence split into three cases? To handle i = 0 w i > c w i ≤ c
State optimal substructure in plain words. The best answer to the whole can be built from best answers to its parts.
Why is the combining operator sometimes + max It matches what the problem asks — Fibonacci sums two answers, knapsack picks the best of two options.
Where does the master formula Time = (#subproblems)×(work each) come from? From summing the fill-cost over every table cell; if each cell costs the same, the sum becomes count × work-per-cell.
Recursion — the machine DP is built on.Recursion Trees — where overlap becomes visible.Time Complexity Analysis — the meaning of O ( ⋅ ) Memoization vs Tabulation — the two table-filling styles.Divide and Conquer — disjoint subproblems, so no caching help.Greedy Algorithms — commits once, never reconsiders.Knapsack Problem , Longest Common Subsequence , Bellman-Ford — optimal-substructure classics. 
