Dynamic Programming

Motivation: Hotel Scheduling Problem

Problem 1. Given $n+1$ cities $c_0, \ldots, c_n$ with distances $d_i$ between consecutive cities, find a schedule that minimizes hotel costs while respecting a maximum daily travel distance $D$. The cost of staying at $c_i$ is $p_i$, and the cost at $c_n$ is always paid.

Approaches and Pitfalls

Approach 1: Generate All Cases (Inefficient)

function GenerateSchedules(k):
    if k = 0: return {empty schedule}
    S ← GenerateSchedules(k-1)
    S' ← ∅
    for each schedule s ∈ S:
        add version "sleep at ck" to S'
        add version "don't sleep at ck" to S'
    return S'

Problem: The amount of information passed between function calls grows exponentially.

Approach 2: Recursion + Split (Flawed)

If we sleep at an intermediate city $c_i$, split the problem into $[c_0, \ldots, c_i]$ and $[c_i, \ldots, c_n]$.

function BestSchedule(c0, ..., cn):
    sol ← ∞
    if Σdi ≤ D: sol ← min(sol, pn)
    for i ← 1, ..., n-1:
        sol1 ← BestSchedule(c0, ..., ci)
        sol2 ← BestSchedule(ci, ..., cn)
        sol ← min(sol, sol1 + sol2)
    return sol

Problem: Same subproblems are computed multiple times. For example, if the optimal solution sleeps at $c_2, c_4, c_6$, this solution is considered separately when $i=2$, $i=4$, and $i=6$.

Approach 3: Simplified Recursion

Focus on “the last city slept at (excluding $c_n$).”

function BestSchedule(n):
    if n = 0: return p0
    sol ← ∞
    for i ← 0, ..., n-1:
        if Σ(j=i+1 to n) dj ≤ D:
            sol ← min(sol, pn + BestSchedule(i))
    return sol

Correctness: Clear. However, the number of recursive calls is exponential due to overlapping subproblems.

Key observation: The return value depends only on argument $n$, so the same computation repeats every time the function is called with the same $n$.

Memoization

function BestSchedule(n):
    if n = 0: return p0
    if M[n] is defined: return M[n]
    sol ← ∞
    for i ← 0, ..., n-1:
        if Σ(j=i+1 to n) dj ≤ D:
            sol ← min(sol, pn + BestSchedule(i))
    M[n] ← sol
    return sol

create array M
return BestSchedule(n)

The technique of caching return values to avoid redundant computation is called memoization.

Time complexity analysis: The main logic (computing sol) executes at most once per value of $n$ (no circular dependencies). One execution: $O(n)$. Number of distinct inputs: $O(n)$. Overall: $O(n^2)$.

Iterative Dynamic Programming

Observing the recursive structure, we can fill a table in a simple order ($i = 0, 1, \ldots, n$):

M[0] ← 0
for i ← 1, ..., n do
    M[i] ← pi + min{ M[j] | 0 ≤ j ≤ i-1, Σ(k=j+1 to i) dk ≤ D }
return M[n]

($\min \emptyset := +\infty$)

Core Principles of Dynamic Programming

Dynamic Programming:

First define a recurrence satisfied by the optimal solutions of subproblems.

Fill a table by computing subproblems in order from smallest to largest.

Determine the evaluation order to avoid circular dependencies.

Difference from divide-and-conquer: Subproblem sizes typically decrease by only a small amount.
Why pass only small amounts of information between recursive calls: it determines the size of the subproblem table (= running time).
Why “decoupling” matters: we must express the optimal solution to a large problem in terms of optimal solutions to subproblems.

Longest Nondecreasing Subsequence (LNS)

Problem Definition

Problem 2. Given a sequence of integers $a_1, \ldots, a_n$, find the longest nondecreasing subsequence (not necessarily contiguous).

Example: 40 41 2 41 7 8 15 1 3

Subproblem Coupling Issue and Resolution

If we define $\text{OPT}(i)$ as the length of the longest nondecreasing subsequence of $a_1, \ldots, a_i$, a coupling problem arises: when expressing $\text{OPT}(9)$ in terms of $\text{OPT}(i)$ ($i \leq 8$), we cannot tell whether the last value of each subproblem’s solution is $\leq a_9 = 3$.

Resolution — Subproblem Redefinition:

Definition. $\text{OPT}(i)$ = the length of the longest nondecreasing subsequence of $a_1, \ldots, a_i$ that must include $a_i$

“Undoing the last decision”: consider element $a_j$ ($j < i$, $a_j \leq a_i$) directly before $a_i$.

Recurrence

Lemma 1. For all $i \geq 1$:

\[\text{OPT}(i) = \max \begin{cases} 1 \\ \displaystyle\max_{\substack{j:\ 1 \leq j \leq i-1 \\ a_j \leq a_i}} \text{OPT}(j) + 1 & \text{(if such } j \text{ exists)} \end{cases}\]

Two Requirements for Recurrence Design

Exhaustive: The optimal solution must fall into at least one of the cases.
Sound: Each case must correspond to a feasible solution.

Proof of Lemma 1

LHS ≤ RHS: Let $a_{k_1}, \ldots, a_{k_\ell}$ ($k_\ell = i$) be the longest nondecreasing subsequence containing $a_i$.

If $\ell = 1$: $\text{OPT}(i) = 1$, so $\text{LHS} \leq \text{RHS}$.
If $\ell > 1$: Let $j = k_{\ell-1}$. Since $a_{k_1}, \ldots, a_{k_{\ell-1}}$ ends at $a_j$, $\text{OPT}(j) \geq \text{OPT}(i) - 1$, giving $\text{LHS} \leq \text{RHS}$.

LHS ≥ RHS:

$\text{OPT}(i) \geq 1$: The sequence $\lbrace a_i\rbrace$ itself is nondecreasing.
For all $j$ with $a_j \leq a_i$: appending $a_i$ to the subsequence achieving $\text{OPT}(j)$ gives a nondecreasing subsequence of length $\text{OPT}(j)+1$, so $\text{OPT}(i) \geq \text{OPT}(j)+1$.

Therefore $\text{LHS} \geq \text{RHS}$. ∎

Algorithm

M[0] ← 0  (define a0 := -∞)
for i ← 1, ..., n do
    M[i] ← max{ M[j] + 1 | 0 ≤ j ≤ i-1, aj ≤ ai }
return max(M[1], ..., M[n])

Lemma 2. $M[i] = \text{OPT}(i)$.

Proof. Defining $\text{OPT}(0) := 0$ and $a_0 := -\infty$ unifies the recurrence. Proved by induction on $i$. ∎

Theorem 1. The algorithm correctly returns the LNS length in $O(n^2)$ time.

Recovering the Actual Sequence

M[0] ← 0
for i ← 1, ..., n do
    M[i] ← max{ M[j]+1 | 0 ≤ j ≤ i-1, aj ≤ ai }
    prev[i] ← corresponding j (argmax)
last ← argmax{ M[i] | 1 ≤ i ≤ n }
while last ≠ 0:
    push a[last] to stack
    last ← prev[last]
pop everything  (output)

Sequence Alignment

Problem Definition

A problem that quantifies how similar two strings are.

Definition 2. A matching $M \subseteq \lbrace 1,\ldots,m\rbrace \times \lbrace 1,\ldots,n\rbrace$ is a set where each index appears at most once.

Definition 3. A matching is an alignment if there are no crossing pairs: for $(i,j),(i’,j’) \in M$ with $i < i’$, we have $j < j’$.

Definition 4. The cost of an alignment:

Unmatched position (gap): penalty $\delta$

$(i,j) \in M$ with $x_i \neq y_j$: mismatch cost $\alpha_{x_i y_j}$

Problem 3. Find the minimum-cost alignment of two strings $x_1 \cdots x_m$ and $y_1 \cdots y_n$.

Recurrence

Let $\text{OPT}(i,j)$ be the minimum cost alignment of $x_1 \cdots x_i$ and $y_1 \cdots y_j$. The last decision is either $(i,j) \in M$, or at least one of $x_i$ or $y_j$ is unmatched.

Lemma 3. For all $i \geq 1$, $j \geq 1$:

\[\text{OPT}(i,j) = \min \begin{cases} \text{OPT}(i-1,j-1) + \alpha_{x_i y_j} \\ \text{OPT}(i-1,j) + \delta \\ \text{OPT}(i,j-1) + \delta \end{cases}\]

Boundary conditions: $\text{OPT}(0,k) = \text{OPT}(k,0) = k\delta$

Algorithm

M[i,0] ← iδ  for all i
M[0,j] ← jδ  for all j
for i ← 1, ..., m do
    for j ← 1, ..., n do
        M[i,j] ← min(
            M[i-1,j-1] + α(xi, yj),
            M[i-1,j] + δ,
            M[i,j-1] + δ
        )
return M[m,n]

Theorem 2. The algorithm is correct (by induction on $i+j$) and runs in $O(mn)$ time.