Dynamic Programming
CS F364 — Design & Analysis of Algorithms | Summer 2026
String interleaving. For bit strings X = x_1\dots x_m, Y = y_1\dots y_n, and Z = z_1\dots z_{m+n}, we say Z is an interleaving of X and Y if it can be obtained by interleaving the bits of X and Y while preserving left-to-right order.
Example: X=101, Y=01; then 10011 is an interleaving (x_1 x_2 y_1 x_3 y_2), but 11010 is not.
Give an efficient DP algorithm to determine if Z is an interleaving of X and Y.
Analyze its time complexity as a function of m = |X| and n = |Y|.
(i) DP recurrence:
Define c[i][j] = \text{true} iff Z[1..i+j] is an interleaving of X[1..i] and Y[1..j].
Base: c[0][0] = \text{true} (empty strings interleave to empty).
Recurrence: c[i][j] = \begin{cases} c[i-1][j] & \text{if } X[i] = Z[i+j] \text{ and } Y[j] \ne Z[i+j] \\[4pt] c[i][j-1] & \text{if } X[i] \ne Z[i+j] \text{ and } Y[j] = Z[i+j] \\[4pt] c[i-1][j] \lor c[i][j-1] & \text{if } X[i] = Y[j] = Z[i+j] \\[4pt] \text{false} & \text{otherwise} \end{cases} Algorithm: Fill the (m+1)\times(n+1) table c row-by-row. Return c[m][n].
(ii) Complexity: Each cell takes O(1) time. There are (m+1)(n+1) = O(mn) cells. Hence O(mn) time and space.
Petrol pump stops. You drive from Kanyakumari to Hyderabad with petrol pumps at distances x_1, x_2, \dots, x_n from Kanyakumari. Filling up at pump i takes c_i minutes (petrol costs the same everywhere). Your car holds enough petrol for 100 km and you start with a full tank. If you stop at a pump, you must fill the tank completely. Give a DP that minimizes total fill-up time.
Write the recurrence relation, defining every symbol.
Explain how you derived it.
Give memoized non-recursive pseudocode returning the minimum cost.
(i) Recurrence:
Let x_0 = 0 denote Kanyakumari (start) and x_{n+1} = D denote Hyderabad (destination). Let c_0 = 0 (no cost to start with a full tank).
Define \text{OPT}[i] = minimum total fill-up time to reach pump i (or the destination, for i = n+1).
\text{OPT}[0] = 0 \text{OPT}[i] = \min_{\substack{j < i \\ x_i - x_j \le 100}} \bigl( \text{OPT}[j] + c_j \bigr) \quad \text{for } i = 1, \dots, n+1 where c_{n+1} = 0 (no fill-up at destination).
(ii) Derivation: To reach pump i, we must have stopped at some earlier pump j such that the distance x_i - x_j is within the tank’s range (100 km). The total time is the optimal time to reach j plus the fill-up time at j. We minimize over all such j. The base case \text{OPT}[0] = 0 says we start with zero cost.
(iii) Pseudocode (bottom-up DP):
// Input: distances x[0..n], costs c[0..n], destination D
// Output: minimum total fill-up time
x[n+1] = D
c[n+1] = 0
OPT[0] = 0
for i = 1 to n+1:
OPT[i] = INF
for j = i-1 down to 0:
if x[i] - x[j] > 100:
break // further j are even farther
OPT[i] = min(OPT[i], OPT[j] + c[j])
return OPT[n+1]Time: O(n^2) worst-case, since each i checks at most O(n) earlier pumps. Space: O(n).
Subset sum. Given an array X[1..n] of positive numbers and a target t, determine whether any subset of X sums to exactly t.
Give the DP recurrence.
What is the time complexity? Is it a polynomial-time algorithm?
Input: X = \{8,6,7,5,3,10,9\}, t = 15
Output: True (subset \{10,5\})
Input: X = \{11,6,5,1,7,13,12\}, t = 15
Output: False
(i) DP recurrence:
Define S(i, s) = \text{true} iff some subset of X[i..n] sums to exactly s.
\begin{aligned} S(i, 0) &= \text{true} \quad \text{(empty subset sums to 0)} \\ S(i, s) &= \text{false} \quad \text{if } i > n \text{ and } s > 0 \\ S(i, s) &= S(i+1, s) \quad \text{if } s < X[i] \\ S(i, s) &= S(i+1, s) \lor S(i+1, s - X[i]) \quad \text{otherwise} \end{aligned} The answer is S(1, t). Equivalently, we can fill a 2D boolean table of size (n+1) \times (t+1) bottom-up or use a 1D array for space efficiency.
(ii) Complexity: The table has O(n \cdot t) entries, each O(1). Time: O(nt). This is pseudo-polynomial — it is polynomial in n and t, but t can be exponential in the input size (which is n \log t bits). Hence subset sum is NP-complete, and this DP is not a polynomial-time algorithm in the usual sense (it is exponential when t is large).