13.25 Case Studies
This chapter has treated dynamic programming as a toolkit: state design, recurrence construction, memoization, tabulation, counting, optimization, graph DP, interval DP, tree DP, bitmask DP, and trans...
13.25 Case Studies
This chapter has treated dynamic programming as a toolkit: state design, recurrence construction, memoization, tabulation, counting, optimization, graph DP, interval DP, tree DP, bitmask DP, and transition optimizations. The final step is integration. Real problems rarely announce which pattern they require. You have to identify the structure, choose a state, prove the recurrence, and then decide whether the straightforward implementation is sufficient.
This section walks through several compact case studies. Each one emphasizes the design process rather than the memorization of a named algorithm.
Case Study 1: Word Break
Given a string and a dictionary, determine whether the string can be segmented into valid dictionary words.
Example:
s = "leetcode"
dict = {"leet", "code"}
Answer:
true
State Design
Define:
$$ dp[i] $$
as:
whether s[0...i) can be segmented
into dictionary words
The final answer is:
$$ dp[n] $$
Recurrence
To compute dp[i], try every previous split point j.
If:
dp[j] is true
and:
s[j...i) is in the dictionary
then:
$$ dp[i]=true $$
Implementation:
func WordBreak(s string, dict map[string]bool) bool {
n := len(s)
dp := make([]bool, n+1)
dp[0] = true
for i := 1; i <= n; i++ {
for j := 0; j < i; j++ {
if dp[j] && dict[s[j:i]] {
dp[i] = true
break
}
}
}
return dp[n]
}
Analysis
There are:
$$ O(n) $$
states.
Each state checks up to:
$$ O(n) $$
split points.
Ignoring substring construction costs, time is:
$$ O(n^2) $$
Memory is:
$$ O(n) $$
This is a feasibility DP over prefixes.
Case Study 2: House Robber
Given a line of houses, each containing money, choose houses so that no two adjacent houses are robbed.
Example:
values = [2, 7, 9, 3, 1]
Answer:
12
by taking:
2 + 9 + 1
State Design
Define:
$$ dp[i] $$
as:
maximum money obtainable
from the first i houses
Recurrence
For house (i), either skip it or take it.
Skip:
$$ dp[i-1] $$
Take:
$$ dp[i-2]+value[i-1] $$
Therefore:
$$ dp[i] = \max(dp[i-1], dp[i-2]+value[i-1]) $$
Implementation:
func Rob(values []int) int {
n := len(values)
if n == 0 {
return 0
}
dp := make([]int, n+1)
dp[0] = 0
dp[1] = values[0]
for i := 2; i <= n; i++ {
dp[i] = max(
dp[i-1],
dp[i-2]+values[i-1],
)
}
return dp[n]
}
Space Optimization
Only two previous states are needed.
func RobCompressed(values []int) int {
prev2 := 0
prev1 := 0
for _, value := range values {
current := max(
prev1,
prev2+value,
)
prev2 = prev1
prev1 = current
}
return prev1
}
Memory becomes:
$$ O(1) $$
This is a classic include/exclude optimization DP.
Case Study 3: Unique Paths with Obstacles
Given a grid with obstacles, count paths from the top-left to the bottom-right. Moves are allowed only right and down.
State Design
Define:
$$ dp[i][j] $$
as:
number of valid paths
to cell (i,j)
If a cell is blocked:
$$ dp[i][j]=0 $$
Otherwise:
$$ dp[i][j] = dp[i-1][j] + dp[i][j-1] $$
Implementation
func UniquePathsWithObstacles(grid [][]int) int {
rows := len(grid)
cols := len(grid[0])
dp := make([]int, cols)
if grid[0][0] == 1 {
return 0
}
dp[0] = 1
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
if grid[i][j] == 1 {
dp[j] = 0
continue
}
if j > 0 {
dp[j] += dp[j-1]
}
}
}
return dp[cols-1]
}
This example uses row compression immediately.
The update:
dp[j]
represents paths from above.
The update:
dp[j-1]
represents paths from the left.
Case Study 4: Palindrome Partitioning Minimum Cuts
Given a string, cut it into the fewest number of palindromic substrings.
Example:
s = "aab"
Answer:
1
because:
aa | b
Step 1: Precompute Palindromes
Define:
$$ pal[l][r] $$
as:
whether s[l...r] is a palindrome
Recurrence:
$$ pal[l][r] = s[l]=s[r] \land pal[l+1][r-1] $$
Short substrings are base cases.
Step 2: DP Over Prefixes
Define:
$$ dp[i] $$
as:
minimum cuts needed
for s[0...i)
Transition:
If:
s[j...i)
is a palindrome, then:
$$ dp[i] = \min(dp[i], dp[j]+1) $$
To count cuts rather than pieces, initialize:
$$ dp[0] = -1 $$
so that one whole palindrome needs zero cuts.
Implementation
func MinCutPalindrome(s string) int {
n := len(s)
pal := make([][]bool, n)
for i := range pal {
pal[i] = make([]bool, n)
}
for length := 1; length <= n; length++ {
for l := 0; l+length-1 < n; l++ {
r := l + length - 1
if s[l] == s[r] &&
(length <= 2 || pal[l+1][r-1]) {
pal[l][r] = true
}
}
}
const inf = int(1e9)
dp := make([]int, n+1)
for i := 1; i <= n; i++ {
dp[i] = inf
}
dp[0] = -1
for i := 1; i <= n; i++ {
for j := 0; j < i; j++ {
if pal[j][i-1] {
dp[i] = min(
dp[i],
dp[j]+1,
)
}
}
}
return dp[n]
}
This case combines interval DP preprocessing with prefix optimization DP.
Case Study 5: Minimum Cost Climbing Stairs
Given a cost for each stair, climb one or two steps at a time. Find the minimum cost to reach the top.
State Design
Define:
$$ dp[i] $$
as:
minimum cost to reach step i
The top is treated as step:
$$ n $$
with no cost.
Transition:
$$ dp[i] = \min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]) $$
Implementation:
func MinCostClimbingStairs(cost []int) int {
n := len(cost)
dp := make([]int, n+1)
for i := 2; i <= n; i++ {
dp[i] = min(
dp[i-1]+cost[i-1],
dp[i-2]+cost[i-2],
)
}
return dp[n]
}
This is a small but useful example of modeling an artificial final state.
Case Study 6: Target Sum
Given an array of numbers, assign + or - signs so the expression equals a target.
Example:
nums = [1, 1, 1, 1, 1]
target = 3
Answer:
5
Direct State
Define:
$$ dp[i][sum] $$
as:
number of ways after processing
first i numbers
to obtain sum
Because sums can be negative, use a map.
func TargetSum(nums []int, target int) int {
dp := map[int]int{
0: 1,
}
for _, x := range nums {
next := map[int]int{}
for sum, count := range dp {
next[sum+x] += count
next[sum-x] += count
}
dp = next
}
return dp[target]
}
This is counting DP over a sparse state space.
Alternative Formulation
The problem can also be transformed into subset sum.
Let:
P = numbers assigned plus
N = numbers assigned minus
We need:
$$ P-N=target $$
and:
$$ P+N=total $$
Solving:
$$ P=\frac{total+target}{2} $$
So the problem becomes:
count subsets with sum P
This formulation is often faster when values are nonnegative and the target range is manageable.
Case Study 7: Longest Path in a DAG
Given a directed acyclic graph, find the longest path length.
State:
$$ dp[u] $$
Meaning:
longest path ending at node u
Process nodes in topological order.
For edge:
$$ u \rightarrow v $$
update:
$$ dp[v]=\max(dp[v],dp[u]+1) $$
Implementation:
func LongestPathDAG(graph [][]int, order []int) int {
n := len(graph)
dp := make([]int, n)
answer := 0
for _, u := range order {
for _, v := range graph[u] {
dp[v] = max(
dp[v],
dp[u]+1,
)
answer = max(answer, dp[v])
}
}
return answer
}
This case shows that DP is not limited to arrays and strings.
Any acyclic dependency graph can support dynamic programming.
Comparing the Case Studies
| Problem | State | Type |
|---|---|---|
| Word Break | dp[i] |
Feasibility |
| House Robber | dp[i] |
Optimization |
| Grid Paths | dp[i][j] |
Counting |
| Palindrome Cuts | pal[l][r], dp[i] |
Interval + prefix |
| Climbing Stairs Cost | dp[i] |
Optimization |
| Target Sum | dp[sum] |
Sparse counting |
| DAG Longest Path | dp[u] |
Graph DP |
The surface problems differ, but the workflow is the same:
define state
derive transition
initialize base cases
choose order
test against small cases
optimize if needed
Takeaway
Dynamic programming becomes practical when treated as a repeatable design process. The case studies in this section show how the same ideas apply across feasibility checks, counting problems, optimization problems, string processing, sparse state spaces, and graph dependencies. The main skill is not memorizing a catalog of recurrences. It is recognizing the shape of the subproblem, choosing the smallest sufficient state, and translating the allowed decisions into transitions. Once that process is internalized, new dynamic programming problems become variations on familiar themes rather than isolated puzzles.