Dynamic Programming: Memoization, Tabulation, and State Optimization

Dynamic Programming (DP) solves complex optimization problems by breaking them down into overlapping subproblems exhibiting optimal substructure, computing each subproblem once, and storing solutions in memory to avoid redundant recomputations.

⚡ Quick Dive

The DP Core Checklist

An optimization problem can be solved with Dynamic Programming if and only if it satisfies:

  1. Optimal Substructure: An optimal solution to the problem contains optimal solutions to its subproblems.
  2. Overlapping Subproblems: Recursive algorithms visit the same subproblems repeatedly (rather than generating unique subproblems).

Classic Dynamic Programming Problems Reference

Problem Recurrence Relation / State Time Complexity Space (Naive / Optimized)
Fibonacci Numbers $dp[i] = dp[i-1] + dp[i-2]$ $O(n)$ $O(n) \to O(1)$
0/1 Knapsack $dp[i][w] = \max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])$ $O(N \cdot W)$ $O(N \cdot W) \to O(W)$
Coin Change (Min Coins) $dp[w] = \min_{c}(dp[w - c] + 1)$ $O(\text{amount} \cdot N)$ $O(\text{amount})$
Longest Common Subsequence $dp[i][j] = dp[i-1][j-1]+1 \text{ if match else } \max(dp[i-1][j], dp[i][j-1])$ $O(M \cdot N)$ $O(M \cdot N) \to O(\min(M, N))$
Edit Distance (Levenshtein) $dp[i][j] = 1 + \min(\text{insert}, \text{delete}, \text{replace})$ $O(M \cdot N)$ $O(M \cdot N) \to O(N)$
Longest Increasing Subsequence Patience sorting with binary search $O(n \log n)$ $O(n)$

📖 Extended Guide

1. Top-Down (Memoization) vs. Bottom-Up (Tabulation)

Top-Down (Memoized Recursion):
Start at Target N ──► Check Cache ──► If miss, Recurse down to Base Cases ──► Store & Return

Bottom-Up (Tabulation):
Start at Base Cases (dp[0], dp[1]) ──► Iteratively compute dp[2], dp[3]... ──► Reach Target dp[N]
  • Top-Down: Intuitive to formulate from mathematical recurrence; computes only needed subproblems; carries recursive call-stack overhead.
  • Bottom-Up: Iterative; avoids recursion stack limits; enables memory optimization by discarding unneeded earlier rows.

2. 0/1 Knapsack: From 2D Matrix to 1D Array

Given $N$ items with weights and values, find maximum value fitting inside knapsack of capacity $W$. Each item can be included at most once.

State Definition: dp[i][w] = maximum value using a subset of items {0...i} with maximum weight w.
Transition:
- Exclude item i: dp[i][w] = dp[i-1][w]
- Include item i: dp[i][w] = dp[i-1][w - weights[i]] + values[i] (if w >= weights[i])

Space Optimization to $O(W)$:

Because row $i$ depends strictly on row $i-1$, we can collapse the matrix into a single 1D array by iterating the weight capacity backward (from $W$ down to $wt[i]$) to prevent using the same item multiple times.

package main

import "fmt"

func Knapsack01(weights, values []int, capacity int) int {
	dp := make([]int, capacity+1)

	for i := 0; i < len(weights); i++ {
		w_i := weights[i]
		v_i := values[i]
		// Iterate BACKWARDS to ensure each item is only counted once
		for w := capacity; w >= w_i; w-- {
			if dp[w-w_i]+v_i > dp[w] {
				dp[w] = dp[w-w_i] + v_i
			}
		}
	}

	return dp[capacity]
}

func main() {
	weights := []int{2, 3, 4, 5}
	values := []int{3, 4, 5, 6}
	capacity := 8
	fmt.Printf("Maximum Knapsack Value: %d\n", Knapsack01(weights, values, capacity)) // 10
}

3. Longest Common Subsequence (LCS)

Used in file diffing (diff, git diff) and DNA sequence alignment (Bioinformatics):

func LongestCommonSubsequence(text1, text2 string) int {
	m, n := len(text1), len(text2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if text1[i-1] == text2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				if dp[i-1][j] > dp[i][j-1] {
					dp[i][j] = dp[i-1][j]
				} else {
					dp[i][j] = dp[i][j-1]
				}
			}
		}
	}

	return dp[m][n]
}

4. Longest Increasing Subsequence ($O(n \log n)$ Patience Sorting)

Instead of the naive $O(n^2)$ DP, maintain an array tails where tails[i] stores the smallest tail of all increasing subsequences of length $i+1$. Use binary search (lower_bound) to update tails in $O(n \log n)$ time.

⌂ All Guides