Recursion, Backtracking and Dynamic Programming #
What is Dynamic Programming? #
- Dynamic Programming (DP): Solve problems by breaking into overlapping subproblems.
- Key Idea: Avoid recomputation by storing results of subproblems.
- Two approaches:
- Top-down (Memoization: recursion + caching)
- Bottom-up (Iterative, table-filling)
DP Workflow (Memoization) #
- Define recursive relation
- Identify base cases
- Store answers in a cache (array)
- Before computing, check cache
- Save result into cache
Example 1: Fibonacci Numbers #
Recursive definition:
$$ F(n) = \begin{cases} 0 & n=0 \ 1 & n=1 \ F(n-1) + F(n-2) & n>1 \end{cases} $$
Fibonacci Code (with Cache) #
#define MAX 50
int memo[MAX];
int fib(int n) {
if (memo[n] != -1) return memo[n];
if (n == 0) return memo[n] = 0;
if (n == 1) return memo[n] = 1;
return memo[n] = fib(n-1) + fib(n-2);
}
⚡ From exponential time → linear time.
Example 2: Grid Paths #
Count ways to reach bottom-right of an m x n
grid, moving only right or down.
Recurrence: $$ ways(m,n) = ways(m-1,n) + ways(m,n-1) $$
Base cases:
ways(0,n) = 1
ways(m,0) = 1
Grid Paths Code #
#define MAX 20
int memo[MAX][MAX];
int paths(int m, int n) {
if (memo[m][n] != -1) return memo[m][n];
if (m == 0 || n == 0) return memo[m][n] = 1;
return memo[m][n] = paths(m-1, n) + paths(m, n-1);
}
Example 3: Longest Common Subsequence (LCS) #
Problem: Given strings X
and Y
, find length of longest subsequence common to both.
Recurrence: $$ LCS(i,j) = \begin{cases} 0 & i=0 \text{ or } j=0 \ LCS(i-1,j-1)+1 & X[i-1] = Y[j-1] \ \max(LCS(i-1,j), LCS(i,j-1)) & \text{otherwise} \end{cases} $$
LCS Code (Memoized) #
#define MAX 100
int memo[MAX][MAX];
int LCS(char *X, char *Y, int i, int j) {
if (i == 0 || j == 0) return 0;
if (memo[i][j] != -1) return memo[i][j];
if (X[i-1] == Y[j-1])
return memo[i][j] = 1 + LCS(X, Y, i-1, j-1);
return memo[i][j] =
(LCS(X, Y, i-1, j) > LCS(X, Y, i, j-1) ?
LCS(X, Y, i-1, j) : LCS(X, Y, i, j-1));
}
Example 4: 0/1 Knapsack Problem #
Problem: Given n
items with weights w[i]
and values v[i]
, and capacity W
, maximize total value.
Recurrence: $$ K(n,W) = \begin{cases} 0 & n=0 \text{ or } W=0 \ K(n-1, W) & w[n-1] > W \ \max( v[n-1] + K(n-1, W-w[n-1]), , K(n-1, W) ) & \text{otherwise} \end{cases} $$
Knapsack Code (Memoized) #
#define MAXN 100
#define MAXW 1000
int memo[MAXN][MAXW];
int knap(int n, int W, int w[], int v[]) {
if (n == 0 || W == 0) return 0;
if (memo[n][W] != -1) return memo[n][W];
if (w[n-1] > W)
return memo[n][W] = knap(n-1, W, w, v);
int include = v[n-1] + knap(n-1, W - w[n-1], w, v);
int exclude = knap(n-1, W, w, v);
return memo[n][W] = (include > exclude ? include : exclude);
}
Why Use Memoization? #
- Simple to implement (just add a cache)
- Improves performance drastically
- Natural extension of recursion
- Good stepping stone to iterative DP
Practice Problems #
- Fibonacci (memoized)
- Grid Paths (m x n grid)
- Longest Common Subsequence
- Minimum Coin Change
- Knapsack Problem
- Edit Distance
Summary #
- DP = Recursion + Caching
- Identify overlapping subproblems
- Store answers in arrays
- Examples: Fibonacci, Grid Paths, LCS, Knapsack
- Powerful tool for optimization problems