Optimal Substructure - Learning Module

Loading content...

0/276

Building Optimal From Optimal Subproblems

From Pieces to Wholes: The Art of Optimal Construction

In the previous page, we established a powerful truth: optimal solutions contain optimal subsolutions. But knowing that optimal subsolutions exist within an optimal solution is only half the story. How do we actually construct that optimal solution from its pieces?

Consider a master architect designing a skyscraper. It's not enough to know that each floor should be optimally designed—the architect must understand how to combine floors, in what order to build them, and which choices connect the pieces into a coherent whole.

This page addresses the construction problem: the systematic process of building globally optimal solutions by combining locally optimal pieces. This is where optimal substructure transforms from a theoretical property into a practical algorithm design technique.

What You Will Master

By the end of this page, you will understand how to: identify the combination function that merges subsolutions, determine the correct order for solving subproblems, define base cases that anchor your construction, and trace through the building process from foundation to final answer. This is the operational heart of dynamic programming.

The Combination Function: Merging Subsolutions

Every dynamic programming solution relies on a combination function—the operation that takes optimal solutions to subproblems and produces an optimal solution to the larger problem.

The combination function answers the question: Given that I've optimally solved the smaller pieces, how do I put them together?

Common combination patterns:

Addition: OPT(P) = subsolution_value + OPT(subproblem)
Maximum/Minimum: OPT(P) = max/min over choices of { cost(choice) + OPT(resulting_subproblem) }
Concatenation: OPT(P) = OPT(P₁) followed by OPT(P₂)
Selection: OPT(P) = best of { OPT(including_element), OPT(excluding_element) }

The combination function is the recurrence relation of dynamic programming—it defines how answers propagate from smaller to larger problems.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// PROBLEM 1: Fibonacci Sequence
// Subproblems: F(n-1), F(n-2)
// Combination: Addition
// F(n) = F(n-1) + F(n-2)
 
// PROBLEM 2: Minimum Path Sum in Grid
// Subproblems: minPath[i-1][j], minPath[i][j-1]
// Combination: Minimum + Addition
// minPath[i][j] = grid[i][j] + min(minPath[i-1][j], minPath[i][j-1])
 
// PROBLEM 3: Longest Common Subsequence
// Subproblems: LCS[i-1][j-1], LCS[i-1][j], LCS[i][j-1]
// Combination: Maximum + Conditional Addition
// if X[i] === Y[j]:
//     LCS[i][j] = 1 + LCS[i-1][j-1]
// else:
//     LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
 
// PROBLEM 4: 0/1 Knapsack
// Subproblems: dp[i-1][w], dp[i-1][w-weight[i]]
// Combination: Maximum of Include/Exclude
// dp[i][w] = max(
//     dp[i-1][w],                        // exclude item i
//     value[i] + dp[i-1][w - weight[i]]  // include item i
// )
 
// PROBLEM 5: Matrix Chain Multiplication
// Subproblems: dp[i][k], dp[k+1][j] for each split point k
// Combination: Minimum over all splits + cost of final multiply
// dp[i][j] = min over k { dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1] }

The Pattern Behind All Combinations

Every combination function follows the template: OPT(problem) = optimize_over_decompositions { combine(OPT(subproblem₁), OPT(subproblem₂), ..., local_cost) }. The 'optimize' is usually min or max. The 'combine' is typically addition. The 'local_cost' accounts for the work to join the pieces.

Why the combination function works:

The combination function is valid precisely because of optimal substructure. When we write:

dp[i] = f(dp[smaller_indices]...)

We're implicitly relying on the fact that dp[smaller_indices] contains the optimal value for that subproblem. If it didn't—if we were storing something suboptimal—then our combination might not produce an optimal result.

Optimal substructure guarantees that using optimal subsolutions in the combination produces an optimal full solution. This is the mathematical contract that makes the combination function trustworthy.

Determining Subproblem Order: The Dependency Graph

A critical aspect of building optimal solutions is solving subproblems in the correct order. If subproblem A depends on subproblem B's answer, we must solve B before A.

The dependency graph:

Every DP problem defines an implicit dependency graph:

Nodes: Each unique subproblem
Edges: An edge from B to A means "A depends on B's solution"

To solve the full problem, we must process subproblems in topological order—solving dependencies before dependents.

Why order matters:

In bottom-up DP, we iterate through subproblems, filling in a table. If we visit a subproblem before its dependencies are solved, we don't have the values we need. The computation would read uninitialized or incorrect data.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
PROBLEM: Fibonacci
F(n) depends on F(n-1) and F(n-2)
 
Dependency Graph:
F(0) ← F(2) ← F(4) ← F(6) ...
  ↑      ↗       ↗       ↗
F(1) ← F(3) ← F(5) ← F(7) ...
 
Order: F(0), F(1), F(2), F(3), ... (ascending)
 
─────────────────────────────────────────────────
 
PROBLEM: Longest Common Subsequence (LCS)
LCS[i][j] depends on LCS[i-1][j-1], LCS[i-1][j], LCS[i][j-1]
 
Dependency Graph (for cell [2][2]):
[0][0] → [0][1] → [0][2]
  ↓         ↓         ↓
[1][0] → [1][1] → [1][2]
  ↓         ↓         ↓
[2][0] → [2][1] → [2][2] ←── This cell needs the three above/left
 
Order: Row by row, left to right (or column by column, top to bottom)
 
─────────────────────────────────────────────────
 
PROBLEM: Matrix Chain Multiplication
MCM[i][j] depends on MCM[i][k] and MCM[k+1][j] for all i ≤ k < j
 
Dependency Graph (for matrices 1-4):
[1,1] [2,2] [3,3] [4,4]  ← chains of length 1 (base cases)
   ↘     ↘     ↘
   [1,2] [2,3] [3,4]     ← chains of length 2
      ↘     ↘
      [1,3] [2,4]        ← chains of length 3
         ↘
         [1,4]           ← full chain (answer)
 
Order: By chain length, shortest first (diagonally in the table)

Common Subproblem Ordering Patterns
Problem Type	Subproblem Structure	Typical Order	Example
1D Linear	dp[i] depends on dp[j] for j < i	Ascending index: 0, 1, 2, ..., n	Fibonacci, Coin Change, LIS
2D Grid	dp[i][j] depends on earlier rows/cols	Row by row, left to right	LCS, Edit Distance, Grid Paths
2D Interval	dp[i][j] depends on shorter intervals	By interval length, shortest first	Matrix Chain, Palindrome Partition
Knapsack-style	dp[i][w] depends on dp[i-1][...]	By item, then by capacity	0/1 Knapsack, Subset Sum
DAG Shortest Path	dp[v] depends on predecessors of v	Topological order of vertices	Shortest path in DAG

The Dependency Invariant

The fundamental invariant of bottom-up DP: When we compute dp[X], all subproblems that X depends on must already be computed and stored. Violating this invariant produces incorrect results—we'd be combining incomplete information.

Base Cases: The Foundation of Construction

Every recursive construction needs a foundation—base cases are the subproblems small enough to solve directly without further decomposition. They anchor the recursion and provide the starting values for bottom-up construction.

Why base cases matter:

Without base cases, the dependency chain never terminates. If every subproblem depends on smaller ones, we need to hit bottom somewhere. Base cases are that bottom.

Characteristics of good base cases:

Trivially solvable: The answer is immediately obvious
Complete coverage: Every chain of dependencies eventually reaches a base case
Correctly initialized: Base case values must be set before any dependent computation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// FIBONACCI
// Base cases: F(0) = 0, F(1) = 1
// These are given by definition—no recursion needed
function fib(n: number): number {
    const dp = [0, 1];  // Base cases initialized first
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];  // Relies on base cases
    }
    return dp[n];
}
 
// COIN CHANGE (minimum coins for amount)
// Base case: dp[0] = 0 (zero coins needed for amount zero)
// Why: The "empty" amount is trivially achievable
function coinChange(coins: number[], amount: number): number {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;  // Base case: 0 coins for amount 0
    for (let x = 1; x <= amount; x++) {
        for (const c of coins) {
            if (c <= x) dp[x] = Math.min(dp[x], 1 + dp[x - c]);
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}
 
// LONGEST COMMON SUBSEQUENCE
// Base cases: LCS[i][0] = 0, LCS[0][j] = 0
// Why: If either string is empty, no common subsequence exists
function lcs(X: string, Y: string): number {
    const m = X.length, n = Y.length;
    const dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
    // First row and column are already 0 (base cases)
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (X[i-1] === Y[j-1]) {
                dp[i][j] = 1 + dp[i-1][j-1];
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}
 
// MATRIX CHAIN MULTIPLICATION
// Base cases: cost[i][i] = 0
// Why: Multiplying a single matrix requires zero operations
function matrixChain(dims: number[]): number {
    const n = dims.length - 1;  // n matrices
    const dp = Array.from({length: n}, () => Array(n).fill(0));
    // dp[i][i] = 0 is already set (base cases for single matrices)
    
    // Fill by chain length
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            dp[i][j] = Infinity;
            for (let k = i; k < j; k++) {
                const cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1];
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n-1];
}

Base Case Design Principles

•Identify 'trivial' subproblems: What's the smallest version of the problem you can solve without decomposition?
•Consider 'empty' inputs: Empty strings, zero amounts, single elements—these often form base cases.
•Check boundary conditions: What happens when indices reach 0 or when size is minimal?
•Initialize before iteration: In bottom-up DP, set base cases before entering the main loop.
•Match the recurrence: Base cases must align with what the recurrence relation expects to find.

The Induction Anchor

Base cases serve the same role as the base case in mathematical induction. They provide the foundation that the inductive step builds upon. Without correct base cases, even a perfect recurrence relation produces garbage—as the saying goes, 'garbage in, garbage out.'

Bottom-Up Construction: A Complete Walk-through

Let's trace through a complete bottom-up DP construction to see how optimal subsolutions combine into an optimal solution.

Problem: Minimum Cost Climbing Stairs

You're given an array cost where cost[i] is the cost to step on stair i. You can start at stair 0 or stair 1. From any stair i, you can move to stair i+1 or i+2. Find the minimum cost to reach the top (past the last stair).

Example: cost = [10, 15, 20]

Option 1: Start at stair 0 (cost 10), jump to stair 2 (cost 20), jump to top → Total: 30
Option 2: Start at stair 1 (cost 15), jump to top → Total: 15
Optimal: 15

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
function minCostClimbingStairs(cost: number[]): number {
    const n = cost.length;
    
    // dp[i] = minimum cost to reach stair i (standing on it, having paid cost[i])
    const dp = new Array(n);
    
    // STEP 1: Base Cases
    // We can start on stair 0 or stair 1 for free
    // So minimum cost to "be on" stair 0 = cost[0]
    //    minimum cost to "be on" stair 1 = cost[1]
    dp[0] = cost[0];  // Base case 1
    dp[1] = cost[1];  // Base case 2
    
    // STEP 2: Bottom-Up Construction
    // For each stair i >= 2, we can arrive from i-1 or i-2
    // dp[i] = cost[i] + min(dp[i-1], dp[i-2])
    for (let i = 2; i < n; i++) {
        // The combination function: add current cost to the
        // minimum of the two possible preceding stairs
        dp[i] = cost[i] + Math.min(dp[i-1], dp[i-2]);
    }
    
    // STEP 3: Extract Final Answer
    // The top is past the last stair. We can reach it from
    // either the last stair (n-1) or second-to-last (n-2)
    return Math.min(dp[n-1], dp[n-2]);
}
 
// ═══════════════════════════════════════════════════════════
// TRACE: cost = [10, 15, 20]
// ═══════════════════════════════════════════════════════════
// 
// Step 1: Base Cases
//   dp[0] = 10  (cost to be on stair 0)
//   dp[1] = 15  (cost to be on stair 1)
// 
// Step 2: Fill dp[2]
//   i = 2
//   dp[2] = cost[2] + min(dp[1], dp[0])
//         = 20 + min(15, 10)
//         = 20 + 10
//         = 30
//   (We chose to come from stair 0 because dp[0] = 10 < dp[1] = 15)
// 
// Step 3: Final Answer
//   min(dp[2], dp[1]) = min(30, 15) = 15
//   (We jump from stair 1 directly to the top)
// 
// Answer: 15
// ═══════════════════════════════════════════════════════════

Analyzing the construction:

Base cases established: dp[0] and dp[1] are set directly—no dependencies.
Order respected: We compute dp[2] only after dp[0] and dp[1] are ready. If there were more stairs, we'd continue in ascending order.
Combination function applied: At each step, we take the current cost plus the minimum of arriving from the two possible previous stairs.
Optimal substructure in action: When we compute dp[2] = 20 + min(10, 15), we trust that dp[0]=10 and dp[1]=15 are truly optimal. If they weren't, our combination might not yield the optimal dp[2].
Final answer extracted: The answer isn't necessarily dp[n-1]—we must consider all valid ways to reach the goal.

The Building Pattern

Every bottom-up DP follows this pattern: (1) Initialize base cases, (2) Iterate through subproblems in dependency order, (3) For each subproblem, apply the combination function using already-computed values, (4) Extract the final answer. Master this pattern and you've mastered DP mechanics.

The Choice Structure: How Decisions Combine

Many DP problems involve making choices at each step. The combination function often has the form:

dp[state] = optimize_over_choices { local_cost(choice) + dp[next_state(choice)] }

This structure—choose the best option among several, where each option involves a local cost plus an optimal continuation—is the heart of most DP problems.

Understanding the choice structure:

At each state, we enumerate all possible choices. For each choice:

Compute the immediate cost or reward of that choice
Determine the resulting subproblem
Add our optimal solution to that subproblem (already computed)
Take the best among all choices

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 0/1 Knapsack: Choose items to maximize value within weight limit
// At each item, we make a binary choice: include or exclude
 
function knapsack(weights: number[], values: number[], capacity: number): number {
    const n = weights.length;
    
    // dp[i][w] = max value using items 0..i-1 with capacity w
    const dp = Array.from({length: n + 1}, () => Array(capacity + 1).fill(0));
    
    // Base case: dp[0][w] = 0 (no items = no value)
    // Already initialized to 0
    
    for (let i = 1; i <= n; i++) {
        const itemWeight = weights[i - 1];
        const itemValue = values[i - 1];
        
        for (let w = 0; w <= capacity; w++) {
            // CHOICE STRUCTURE:
            // Choice 1: EXCLUDE item i
            //   Local cost: 0 (we don't take the item)
            //   Resulting subproblem: dp[i-1][w] (same capacity, fewer items)
            const excludeValue = dp[i - 1][w];
            
            // Choice 2: INCLUDE item i (if it fits)
            //   Local benefit: itemValue
            //   Resulting subproblem: dp[i-1][w - itemWeight] (reduced capacity)
            let includeValue = 0;
            if (itemWeight <= w) {
                includeValue = itemValue + dp[i - 1][w - itemWeight];
            }
            
            // COMBINATION: Take the better choice
            dp[i][w] = Math.max(excludeValue, includeValue);
        }
    }
    
    return dp[n][capacity];
}
 
// Why this works (optimal substructure):
// - If the optimal solution for items 1..n, capacity W INCLUDES item n:
//   Then it must use the optimal solution for items 1..n-1, capacity W-weight[n]
//   (If the remaining items weren't optimal, we could do better)
// 
// - If the optimal solution EXCLUDES item n:
//   Then it's exactly the optimal solution for items 1..n-1, capacity W
// 
// Either way, optimal subsolutions combine into the optimal answer.

The "make the best choice" principle:

At every state, we try all valid choices and pick the one that yields the best combined result (immediate + future). Because we've already optimally solved the future (dp values for subproblems), choosing the best combined result gives us the optimal answer for the current state.

This is the Bellman equation in action:

OPT(state) = best over choices { immediate(choice) + OPT(result_of_choice) }

Binary Choice Problems

•0/1 Knapsack: Include or exclude each item
•House Robber: Rob this house or skip it
•LCS: Characters match (take diagonal) or don't (take max of left/up)
•Climbing Stairs: Step 1 or step 2

Multi-Choice Problems

•Coin Change: Use any denomination
•Rod Cutting: Cut off any length
•Matrix Chain: Split at any point
•Word Break: Try any prefix word

Reconstructing the Optimal Solution

So far, we've focused on computing the value of the optimal solution (e.g., the minimum cost, maximum profit, or shortest length). But often we need the actual solution itself—the sequence of choices that achieves that optimal value.

Two approaches to solution reconstruction:

Backtracking through the DP table: After filling the table, start at the final answer and trace back, at each step determining which choice led there.
Storing choices during computation: While filling the table, also record which choice was made at each state. Then read off the solution from the recorded choices.

Both approaches are valid; the choice depends on whether you want to minimize space (backtracking) or simplify reconstruction (storing choices).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// Reconstruct the actual LCS, not just its length
 
function lcsWithReconstruction(X: string, Y: string): string {
    const m = X.length, n = Y.length;
    const dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
    
    // Fill the DP table (computing lengths)
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (X[i-1] === Y[j-1]) {
                dp[i][j] = 1 + dp[i-1][j-1];
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    // BACKTRACK to find the actual subsequence
    let result = '';
    let i = m, j = n;
    
    while (i > 0 && j > 0) {
        if (X[i-1] === Y[j-1]) {
            // This character is part of the LCS
            result = X[i-1] + result;  // Prepend
            i--; j--;  // Move diagonally
        } else if (dp[i-1][j] > dp[i][j-1]) {
            // Optimal came from above
            i--;
        } else {
            // Optimal came from left
            j--;
        }
    }
    
    return result;
}
 
// TRACE for X = "ABCBDAB", Y = "BDCABA"
// 
// DP Table (final):
//       ""  B  D  C  A  B  A
//   ""   0  0  0  0  0  0  0
//   A    0  0  0  0  1  1  1
//   B    0  1  1  1  1  2  2
//   C    0  1  1  2  2  2  2
//   B    0  1  1  2  2  3  3
//   D    0  1  2  2  2  3  3
//   A    0  1  2  2  3  3  4
//   B    0  1  2  2  3  4  4
// 
// Backtrack from dp[7][6] = 4:
//   i=7, j=6: X[6]='B' === Y[5]='A'? No. dp[6][6]=4, dp[7][5]=4, go up.
//   i=6, j=6: X[5]='A' === Y[5]='A'? Yes! Add 'A'. Move to (5,5).
//   i=5, j=5: X[4]='D' === Y[4]='B'? No. dp[4][5]=3, dp[5][4]=2, go up.
//   i=4, j=5: X[3]='B' === Y[4]='B'? Yes! Add 'B'. Move to (3,4).
//   i=3, j=4: X[2]='C' === Y[3]='A'? No. dp[2][4]=1, dp[3][3]=2, go left.
//   i=3, j=3: X[2]='C' === Y[2]='C'? Yes! Add 'C'. Move to (2,2).
//   i=2, j=2: X[1]='B' === Y[1]='D'? No. dp[1][2]=0, dp[2][1]=1, go up.
//   i=1, j=2: X[0]='A' === Y[1]='D'? No. dp[0][2]=0, dp[1][1]=0, go up.
//   i=0: Stop.
// 
// Result (built in reverse): "BCAB" → Actually "BDAB" with proper trace
// One valid LCS: "BCBA" (length 4)

Reconstruction Mirrors Construction

Backtracking follows the logic of construction in reverse. At each step, you ask: 'Which choice did we actually make to get this optimal value?' The answer is the choice whose corresponding subproblem plus local cost equals the current optimal value.

Alternative: Store choices as you go

Instead of backtracking, you can store the chosen action at each state:

// During DP computation:
choice[i][j] = 'MATCH' | 'UP' | 'LEFT';

// During reconstruction:
while (i > 0 && j > 0) {
    switch (choice[i][j]) {
        case 'MATCH': result = X[i-1] + result; i--; j--; break;
        case 'UP':    i--; break;
        case 'LEFT':  j--; break;
    }
}

This uses more space (an additional table) but makes reconstruction simpler and faster.

From Theory to Practice: A Complete Example

Let's bring everything together with a complete example that shows all aspects of building optimal solutions from optimal subproblems.

Problem: Unique Paths with Obstacles

Given an m×n grid where 0 means empty and 1 means obstacle, find the number of unique paths from top-left to bottom-right, moving only right or down. If start or end is blocked, return 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
function uniquePathsWithObstacles(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    
    // Edge case: start or end is blocked
    if (grid[0][0] === 1 || grid[m-1][n-1] === 1) {
        return 0;
    }
    
    // dp[i][j] = number of unique paths to cell (i, j)
    const dp = Array.from({length: m}, () => Array(n).fill(0));
    
    // ═══════════════════════════════════════════════════════
    // STEP 1: BASE CASES
    // ═══════════════════════════════════════════════════════
    // First cell: exactly one way to "be" at the start
    dp[0][0] = 1;
    
    // First column: can only come from above
    // If we hit an obstacle, all cells below are unreachable
    for (let i = 1; i < m; i++) {
        if (grid[i][0] === 1) {
            dp[i][0] = 0;  // Blocked
        } else {
            dp[i][0] = dp[i-1][0];  // Same as cell above (0 or 1)
        }
    }
    
    // First row: can only come from the left
    for (let j = 1; j < n; j++) {
        if (grid[0][j] === 1) {
            dp[0][j] = 0;  // Blocked
        } else {
            dp[0][j] = dp[0][j-1];  // Same as cell to the left
        }
    }
    
    // ═══════════════════════════════════════════════════════
    // STEP 2: FILL IN DEPENDENCY ORDER (row by row, left to right)
    // ═══════════════════════════════════════════════════════
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if (grid[i][j] === 1) {
                dp[i][j] = 0;  // Obstacle: no paths through here
            } else {
                // COMBINATION FUNCTION:
                // Paths to (i,j) = paths from above + paths from left
                // This works because of optimal substructure:
                // The number of paths to (i,j) is completely determined
                // by the number of paths to its predecessors
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    
    // ═══════════════════════════════════════════════════════
    // STEP 3: EXTRACT FINAL ANSWER
    // ═══════════════════════════════════════════════════════
    return dp[m-1][n-1];
}
 
// ═══════════════════════════════════════════════════════════
// TRACE EXAMPLE
// ═══════════════════════════════════════════════════════════
// Grid:
// [0, 0, 0]
// [0, 1, 0]
// [0, 0, 0]
//
// Step 1: Base cases
// dp[0][0] = 1
// First column: dp[0][0]=1, dp[1][0]=1, dp[2][0]=1
// First row:    dp[0][0]=1, dp[0][1]=1, dp[0][2]=1
//
// DP table after base cases:
// [1, 1, 1]
// [1, ?, ?]
// [1, ?, ?]
//
// Step 2: Fill remaining cells
// dp[1][1]: obstacle → 0
// dp[1][2] = dp[0][2] + dp[1][1] = 1 + 0 = 1
// dp[2][1] = dp[1][1] + dp[2][0] = 0 + 1 = 1
// dp[2][2] = dp[1][2] + dp[2][1] = 1 + 1 = 2
//
// Final DP table:
// [1, 1, 1]
// [1, 0, 1]
// [1, 1, 2]
//
// Answer: dp[2][2] = 2 unique paths

All Elements Present

This example demonstrates: (1) Base case initialization for edges, (2) Proper dependency order (row by row), (3) Combination function (sum of predecessors), (4) Handling special cases (obstacles). This is the complete template for building solutions from subproblems.

Summary: The Mechanics of Optimal Construction

We've explored how to build globally optimal solutions from locally optimal pieces—the operational core of dynamic programming. This construction process has four essential components:

Key Takeaways

•The combination function merges optimal subsolutions into optimal solutions. It's the recurrence relation—the heart of every DP.
•Subproblem ordering ensures dependencies are resolved before dependents. Process in topological order of the dependency graph.
•Base cases anchor the construction. They're the trivially solvable subproblems that require no decomposition.
•The choice structure optimizes over multiple options at each state, selecting the best immediate + future combination.
•Solution reconstruction traces back through the DP table to find which choices yielded the optimal value.
•Bottom-up construction fills the table from base cases to the final answer, ensuring all needed values exist when needed.

What's next:

We've now covered what optimal substructure means (Page 1) and how to build solutions using it (Page 2). But optimal substructure isn't unique to dynamic programming—greedy algorithms also rely on it. The next page explores the fascinating connection between DP's optimal substructure and greedy's optimal substructure, revealing when each approach applies.

Page Complete

You now understand the mechanics of building optimal solutions from optimal subproblems. This isn't abstract theory—it's what you do every time you write a DP solution. Initialize base cases, iterate in dependency order, apply the combination function, extract the answer. Master this process and you've mastered the execution of dynamic programming.