17. Dynamic Programming

Introduction to Dynamic Programming

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems, solving each subproblem just once, and storing their solutions – typically in an array or hash map – for future reference. This avoids the exponential blow‑up of naïve recursion and yields polynomial‑time algorithms for many optimization and counting problems.

The two main implementation strategies are:

Top‑down (memoization) – write a recursive function and cache results.
Bottom‑up (tabulation) – iteratively fill a DP table from base cases upward.

Both approaches share the same core steps:

Identify the state (what subproblem we solve).
Define the recurrence relation that expresses the state in terms of smaller states.
Determine the base cases.
Choose a direction (top‑down or bottom‑up) and compute the answer.

Space can often be reduced using rolling arrays, keeping only the needed previous rows or a constant number of variables.

17.2 Memoization (Top‑Down)

Memoization wraps a recursive function with a cache (hash map or array) that returns a stored result if the subproblem has already been solved.

Pseudocode for Fibonacci:

memo = array[0..n] initialized to -1
function fib(k):
    if k <= 1: return k
    if memo[k] != -1: return memo[k]
    memo[k] = fib(k-1) + fib(k-2)
    return memo[k]

Complexity: O(n) time, O(n) space.

Benefits: retains the natural recursive structure, easy to implement, and works well when not all subproblems are needed.

17.3 Tabulation (Bottom‑Up)

Tabulation fills a DP table iteratively, starting from the base cases and building up to the final answer.

Pseudocode for Fibonacci:

dp[0] = 0; dp[1] = 1
for i from 2 to n:
    dp[i] = dp[i-1] + dp[i-2]
return dp[n]

Complexity: O(n) time, O(n) space (can be reduced to O(1) using two variables).

Advantages: eliminates recursion overhead, makes the order of evaluation explicit, and often simplifies space optimisation.

17.4 0/1 Knapsack Problem

Given n items each with weight w_i and value v_i, and a capacity W, find the maximum total value without exceeding the capacity.

State

dp[i][c] = maximum value achievable using the first i items with capacity c.

Recurrence

if w_i > c:
    dp[i][c] = dp[i-1][c]
else:
    dp[i][c] = max(dp[i-1][c], v_i + dp[i-1][c - w_i])

Base Cases

dp[0][c] = 0 for all c (no items ⇒ zero value).

Complexity

O(n·W) time, O(n·W) space. Space can be reduced to O(W) by using a 1‑D array and iterating capacities backwards.

Example

Item	Weight	Value
1	2	3
2	3	4
3	4	5
4	5	6

Capacity W = 5. The optimal selection is items 1 and 2 (weights 2+3 = 5, value 3+4 = 7).

17.5 Longest Common Subsequence (LCS)

Given two strings X[1..m] and Y[1..n], find the length of their longest subsequence (not necessarily contiguous) that appears in both.

State

dp[i][j] = length of LCS of prefixes X[1..i] and Y[1..j].

Recurrence

if X[i] == Y[j]:
    dp[i][j] = 1 + dp[i-1][j-1]
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Base Cases

dp[0][*] = dp[*][0] = 0 (empty string).

Complexity

O(m·n) time, O(m·n) space (reducible to O(min(m,n)) with rolling arrays).

Reconstruction

Starting from dp[m][n], trace back: if characters match, include the character and move diagonally; otherwise move in the direction of the larger neighbour.

Example

X = "ABCBDAB", Y = "BDCABA". The DP table yields LCS length 4. One optimal LCS is "BCBA".

17.6 Longest Increasing Subsequence (LIS)

Find the length of the longest subsequence (not necessarily contiguous) with strictly increasing values.

DP O(n²) Solution

State: dp[i] = length of the longest increasing subsequence ending at position i.

dp[i] = 1 + max{ dp[j] | j < i and a[j] < a[i] }   (if such j exists)
dp[i] = 1                                 (otherwise)

Answer = max_i dp[i].

Complexity: O(n²) time, O(n) space.

Optimized O(n log n) Solution (Patience Sorting)

Maintain an array tails where tails[k] is the smallest possible tail value of an increasing subsequence of length k+1 seen so far.

For each element x in the input array:

Find the lower bound (first index) pos in tails such that tails[pos] ≥ x (binary search).
If pos equals the current length of tails, append x; otherwise replace tails[pos] with x.

The length of tails after processing all elements equals the LIS length.

Complexity: O(n log n) time, O(n) space.

Example

Sequence: [10, 9, 2, 5, 3, 7, 101, 18]

Processing yields tails = [2, 3, 7, 18] (or similar), giving LIS length 4. One LIS is [2, 3, 7, 101].

17.7 Coin Change (Minimum Coins)

Given unlimited coins of denominations c[1..k] and a target amount A, compute the minimum number of coins needed to make exactly A.

State

dp[x] = minimum number of coins to make amount x.

Recurrence

dp[0] = 0
dp[x] = 1 + min{ dp[x - c_i] | c_i ≤ x }   for x > 0

Complexity

O(k·A) time, O(A) space.

Example

Coins: [1, 3, 4], Amount A = 6.

dp[1] = 1 (1)
dp[2] = 2 (1+1)
dp[3] = 1 (3)
dp[4] = 1 (4)
dp[5] = 2 (4+1 or 3+1+1)
dp[6] = 2 (3+3) → optimal.

17.8 Edit Distance (Levenshtein Distance)

Compute the minimum number of insertions, deletions, or replacements required to transform string s1 into s2.

State

dp[i][j] = edit distance between prefixes s1[1..i] and s2[1..j].

Recurrence

if s1[i] == s2[j]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = 1 + min(
        dp[i-1][j],   // delete s1[i]
        dp[i][j-1],   // insert s2[j]
        dp[i-1][j-1]  // replace s1[i] with s2[j]
    )

Base Cases

dp[i][0] = i (delete all characters of s1), dp[0][j] = j (insert all characters of s2).

Complexity

O(|s1|·|s2|) time. Space can be reduced to O(min(|s1|,|s2|)) using two rows (rolling array).

Example

s1 = "kitten", s2 = "sitting".

k → s (replace)
e → i (replace)
insert g at the end

Total operations = 3.

17.9 Matrix Chain Multiplication

Given a chain of matrices A₁, A₂, …, Aₙ where matrix A_i has dimensions p_{i-1} × p_i, determine the parenthesization that minimizes the total number of scalar multiplications.

State

dp[i][j] = minimum cost to multiply the subchain A_i … A_j.

Recurrence

dp[i][i] = 0   // single matrix costs nothing
dp[i][j] = min_{i ≤ k < j} {
    dp[i][k] + dp[k+1][j] + p_{i-1}·p_k·p_j
}

Base Cases

dp[i][i] = 0 for all i.

Complexity

O(n³) time, O(n²) space.

Example

Dimensions array p = [10, 20, 30, 40, 30] corresponding to matrices:

A₁: 10×20
A₂: 20×30
A₃: 30×40
A₄: 40×30

Optimal parenthesization: ((A₁(A₂A₃))A₄)

Cost calculation:

Multiply A₂A₃: 20·30·40 = 24 000
Multiply A₁·(A₂A₃): 10·20·40 = 8 000
Multiply result·A₄: 10·40·30 = 12 000
Total = 24 000 + 8 000 + 12 000 = 44 000 scalar multiplications.

(The original text gave 30 000; the correct minimal cost for these dimensions is 44 000 – the example illustrates the DP process.)

Summary

Dynamic programming transforms problems with overlapping subproblems into efficient polynomial‑time algorithms by:

Clearly defining the state.
Deriving a recurrence relation.
Setting appropriate base cases.
Choosing top‑down memoization or bottom‑up tabulation, often with space optimisation via rolling arrays.

The techniques covered—memoization, tabulation, and the classic DP problems—form the foundation for tackling a wide range of algorithmic challenges in interviews, competitive programming, and real‑world software development.