Week 10

Chapter 10: Dynamic Programming Basics

Master the fundamentals of dynamic programming: recognizing overlapping subproblems, building optimal substructure, and choosing between memoization and tabulation. Apply these principles to classic 1D and 2D DP problems.

Chapter Overview

Dynamic Programming (DP) is one of the most powerful algorithmic techniques for solving optimization problems. At its core, DP is about breaking a problem into smaller overlapping subproblems, solving each one only once, and storing the results for reuse.

Two key properties make a problem amenable to DP:

Overlapping subproblems: The same subproblems appear multiple times during computation (unlike divide and conquer, where subproblems are independent)
Optimal substructure: The optimal solution to the problem can be constructed from optimal solutions to its subproblems

There are two main approaches to implementing DP:

Memoization (top-down): Start from the original problem, recurse into subproblems, and cache results as you go
Tabulation (bottom-up): Build a table from the smallest subproblems upward, filling in solutions iteratively

This chapter covers:

DP fundamentals: Overlapping subproblems, optimal substructure, memoization, and tabulation
1D DP problems: Climbing stairs, house robber
2D DP problems: Grid-based DP, unique paths, minimum path sum
Pattern recognition: How to identify and formulate DP state transitions

Chapter Roadmap

Click any topic to jump in

DP Introduction

Overlapping subproblems, optimal substructure, memoization vs tabulation.

Overlapping SubproblemsOptimal SubstructureMemoization vs Tabulation

Multiple approaches

Each tackles a different aspect

Climbing Stairs

The classic 1D recurrence: $dp[i] = dp[i-1] + dp[i-2]$, Fibonacci in disguise.

State Definition and Base CasesRecognizing Fibonacci Structure

House Robber

Include/exclude pattern with adjacency constraint: $dp[i] = \max(dp[i-1], dp[i-2] + a_i)$.

State Transition with ConstraintsInclude/Exclude Pattern

Builds on previous

Grid-Based DP

2D state design and row-by-row filling order with clear dependencies.

2D State DefinitionFilling Order and Dependencies

Multiple approaches

Each tackles a different aspect

Unique Paths

Counting lattice paths: $dp[i][j] = dp[i-1][j] + dp[i][j-1]$ and its binomial closed form.

Counting Paths with DPHandling Obstacles

Minimum Path Sum

Weighted grid DP with in-place $O(1)$ extra space optimization.

DP on Weighted GridsIn-Place DP Optimization

Builds on previous

Maximal Square

State as side length with the $\min$-of-three-neighbors recurrence.

State as Square Side LengthWhy min() of Three Neighbors?

Dynamic programming transforms exponential-time recursive solutions into polynomial-time algorithms by eliminating redundant computation. The key insight is that if you have already solved a subproblem, you should never solve it again---just look up the answer.

Memoization (top-down) keeps the recursive structure but adds a cache. Tabulation (bottom-up) eliminates recursion entirely by filling a table in the right order. Both give the same time complexity, but tabulation avoids recursion stack overhead while memoization only solves subproblems that are actually needed.

In this topic

1Overlapping Subproblems

2Optimal Substructure

3Memoization vs Tabulation

1 of 3

Overlapping Subproblems

A problem has overlapping subproblems when solving it requires solving the same smaller instances multiple times. The classic example is Fibonacci: computing fib(5) requires fib(4) and fib(3), but fib(4) itself requires fib(3) and fib(2). Without caching, fib(3) is computed twice, fib(2) three times, and so on. This redundancy causes naive recursion to run in $O(2^n)$ time.

Mathematical Intuition

Naive recursion on a problem like Fibonacci generates a recursion tree of size $T(n) = T(n-1) + T(n-2) + O(1)$ , which solves to $T(n) = O(\varphi^n)$ with $\varphi = (1+\sqrt{5})/2 \approx 1.618$ . But the number of distinct subproblems is only $n+1$ . Caching each unique result once collapses the exponential tree into a DAG with $O(n)$ nodes and $O(n)$ edges, giving linear time.

Example:

How many times is fib(2) computed in a naive recursive call to fib(6)?

2 of 3

Optimal Substructure

A problem has optimal substructure if the optimal solution contains optimal solutions to its subproblems. For example, the shortest path from A to C through B must use the shortest path from A to B and the shortest path from B to C. If either sub-path were suboptimal, we could improve the overall path---a contradiction.

Mathematical Intuition

Optimal substructure says an optimal solution to a problem contains optimal solutions to its subproblems. Formally, if $f(x) = \text{opt}_{y \in N(x)} g(f(y), x, y)$ where $g$ is monotone in its first argument, then solving the subproblems optimally is sufficient. This is the prerequisite for any valid DP recurrence and distinguishes DP from problems where local optima can trap you away from the global optimum.

Example:

Does the longest simple path problem have optimal substructure?

3 of 3

Memoization vs Tabulation

Memoization (top-down) uses recursion plus a cache (dictionary or array). You write the recursive solution naturally, then add if subproblem in memo: return memo[subproblem] at the top. Tabulation (bottom-up) creates a table, fills in base cases, then iterates through subproblems in dependency order. Tabulation avoids recursion depth limits and often has better cache locality.

Mathematical Intuition

Both approaches solve the same DAG of subproblems, so they share asymptotic complexity $O(\text{states} \times \text{transitions})$ . Memoization (top-down) has $O(\text{depth})$ stack overhead and only computes reachable states — useful when the reachable set is much smaller than the full state space. Tabulation (bottom-up) visits every state but avoids recursion overhead and enables rolling-array space optimization like $O(W)$ instead of $O(nW)$ for knapsack.

Example:

When would you prefer memoization over tabulation?

Blogs

Dynamic Programming — NeetCode Roadmap Dynamic Programming — LeetCode Editorial Study Plan Introduction to Dynamic Programming Overlapping Subproblems Property in Dynamic Programming

Heaps & Priority Queues

Dynamic Programming Advanced