14. Dynamic Programming

Exercises

14.1-1

Available in the latest revision of the IM.

14.1-2

Available in the latest revision of the IM.

14.1-3

Available in the latest revision of the IM.

14.1-4

Available in the latest revision of the IM.

14.1-5

Available in the latest revision of the IM.

14.1-6

Available in the latest revision of the IM.

The solution in the IM sets $F_0=1$ instead of $F_0=0$. Furthermore, it uses $O(n)$ space instead of $O(1)$. The subproblem graph clearly reveals that we only need to keep the last two values to compute the next element of the sequence.

14.2-1

Available in the latest revision of the IM.

14.2-2

Available in the latest revision of the IM.

14.2-3

Available in the latest revision of the IM.

14.2-4

Available in the latest revision of the IM.

14.2-5

Available in the latest revision of the IM.

14.2-6

Available in the latest revision of the IM.

14.3-1

Available in the latest revision of the IM.

14.3-2

Available in the latest revision of the IM.

14.3-3

Available in the latest revision of the IM.

14.3-4

The IM solution is broken, as it doesn't select $k$ to minimize the quantity $p_{i-1} p_k p_j$.

Let $p_0 = 1, p_1 = 2, p_2 = 10, p_3 = 3$. The greedy strategy would pick $k=1$, resulting in the parenthesization $A_1(A_2A_3)$ that costs 66. Nonetheless, computing the product as $(A_1A_2)A_3$ costs only 50.

14.3-5

Available in the latest revision of the IM.

14.4-1

Available in the latest revision of the IM.

14.4-2

Available in the latest revision of the IM.

14.4-3

Available in the latest revision of the IM.

The code in the IM lacks the base cases (when $i=0 \lor j=0$ then $c_{ij}=0$).

14.4-4

Available in the latest revision of the IM.

14.4-5

Available in the latest revision of the IM.

★ 14.4-6

The solution is available here. To handle duplicates turn each number into an ordered pair $(a_i,i)$, where $i$ is its index. This converts the problem of finding the longest monotonically increasing subsequence of a sequence of $n$ numbers into finding the longest strictly increasing subsequence of a sequence of $n$ ordered pairs.

14.5-1

Available in the latest revision of the IM.

14.5-2

Available in the latest revision of the IM.

14.5-3

Available in the latest revision of the IM.

★ 14.5-4

Using Knuth's optimization, the innermost loop (which searches for the optimal root) no longer runs from $i$ to $j$ (see line 10 of the Optimal-BST function). Instead, it only searches between root[i, j - 1] and root[i + 1, j] for $i<j$. When $i=j$ then root[i, i] = i. Observe that these entries are already filled in, since they are related to intervals of smaller lengths.

For more details consult the tutorial about OBST. Section 2.1.2 derives the $O(n^2)$ upper bound, which matches the lower bound, too. The provided sum massively telescopes, which ensures the $\Theta(n^2)$ running time. The paper also contains the proof of the monotonicity of roots.

Problems

14-1 Longest simple path in a directed acyclic graph

Available in the latest revision of the IM.

The alternative solution in the IM to broken. Since the direction is flipped, we cannot use forward references as in the top-down variant. Below is the fixed version.

Longest-Path(G, s, t)
1  let dist[1 : n] and prev[1 : n] be new arrays
2  topologically sort the vertices of G
3  for i = 1 to |G.V|
4      dist[i] = -∞
5      prev[i] = NIL
6  dist[s] = 0
7  for each u in topological order, starting from s
8      for each edge (u, v) in G.Adj[u]
9          if dist[u] + w(u, v) > dist[v]
10             dist[v] = dist[u] + w(u, v)
11             prev[v] = u    // Point backward from v to u
12 if dist[t] == -∞
13     print "No path exists"
14 else print "The longest distance is " dist[t]
15     Print-Path-Backward(s, t, prev)

14-2 Longest palindrome subsequence

Available in the latest revision of the IM.

14-3 Bitonic euclidean traveling-salesperson problem

Available in the latest revision of the IM.

The solution in the IM prints out the tour in opposite direction, starting from the rightmost point. Of course, this doesn't change the essence of the problem.

14-4 Printing neatly

Available in the latest revision of the IM.

There is a small error in the text about reconstructing the sequene of words. Namely, the second-to-last line starts at p[p[n] - 1] and goes through word p[n]-1.

14-5 Edit distance

Available in the latest revision of the IM.

14-6 Planning a company party

Available in the latest revision of the IM.

14-7 Viterbi algorithm

a.

The problem asks us to find a valid path through a graph that matches a specific sequence of edge labels. We can model this using a layer-by-layer approach similar to Breadth-First Search (BFS), combined with the memoization aspect of dynamic programming.

We can solve this by maintaining a set of "reachable states" at each step of the sequence. Let $S_i$ be the set of all vertices we could possibly be at after successfully traversing the first $i$ sounds of the sequence $s$.

• Base Case: At step 0 (before making any moves), the only reachable vertex is the starting vertex $v_0$. Thus, $S_0 = \{v_0\}$.

• Transitions: To compute $S_i$ (the reachable vertices after matching the $i$-th sound, $\sigma_i$), we look at every vertex $u$ in $S_{i-1}$. If there is an outgoing edge from $u$ to some vertex $v$ with the label $\sigma_i$, we add $v$ to $S_i$.

• Tracking the Path: To reconstruct the path at the end, we maintain a 2D table pred[i, v] that records the predecessor vertex $u$ that led to $v$ at step $i$. It also acts as sort of a "visited" check for a given layer. If at any point $S_i$ becomes empty, it means the sequence cannot be matched, and we return NO-SUCH-PATH. If we successfully reach $S_k$, we can pick any vertex in $S_k$ and backtrack using the pred table to output the path.

Sound-Path(G, v_0, s)
1  k = s.length
2  let pred[1 : k, V] be a new table initialized to NIL
3  let Q be a new empty queue
   // Enqueue the starting vertex at step 0
4  ENQUEUE(Q, (v_0, 0))
5  
6  while Q is not empty
7      (u, i) = DEQUEUE(Q)
8      
9      // If we have successfully matched the entire sequence, reconstruct the path
10     if i == k
11         let path = a new empty list
12         v = u
13         for step = k down to 1
14             prepend v to path
15             v = pred[step, v]
16         prepend v_0 to path
17         return path
18         
19     // Otherwise, evaluate all outgoing edges for the next sound match
20     for each edge (u, v) in G.Adj[u]
21         if label(u, v) == s[i + 1] and pred[i + 1, v] == NIL
22             pred[i + 1, v] = u
23             ENQUEUE(Q, (v, i + 1))
24             
25 return "NO-SUCH-PATH"

The total running time is $O(k(\vert{}V\vert{} + \vert{}E\vert{}))$. The space complexity is $O(k\vert{}V\vert{})$ for storing the pred table (this also upper bounds the size of the queue).

b.

Viterbi-Sound-Path(G, v_0, s)
1  k = s.length
2  let pred[1 : k, V] be a new table initialized to NIL
3  let prob[0 : k, V] be a new table initialized to 0 
4  let Q be a new empty queue
5  prob[0, v_0] = 1
   // Enqueue the starting vertex at step 0
6  ENQUEUE(Q, (v_0, 0))
   
7  while Q is not empty
8      (u, i) = DEQUEUE(Q)
       
9      if i < k
10         for each edge (u, v) in G.Adj[u]
11             if label(u, v) == s[i + 1]
12                 new_prob = prob[i, u] * p(u, v)
                   
13                 // If this is the absolute first time we reach v at step i + 1
14                 if pred[i + 1, v] == NIL
15                     prob[i + 1, v] = new_prob
16                     pred[i + 1, v] = u
17                     ENQUEUE(Q, (v, i + 1))
                       
18                 // Otherwise, if we found a strictly more probable path
19                 elseif new_prob > prob[i + 1, v]
20                     prob[i + 1, v] = new_prob
21                     pred[i + 1, v] = u

   // Find the destination vertex with the highest probability
22 max_prob = -1
23 best_v = NIL
24 for each v in V
       // Check pred to ensure the vertex was actually reached
25     if pred[k, v] != NIL and prob[k, v] > max_prob
26         max_prob = prob[k, v]
27         best_v = v

28 if best_v == NIL
29     return "NO-SUCH-PATH"
   
   // Reconstruct the most probable path
30 let path = a new empty list
31 v = best_v
32 for step = k down to 1
33     prepend v to path
34     v = pred[step, v]
35 prepend v_0 to path
36 return path

Because the queue enforces a strict layer-by-layer traversal, by the time a pair $(v, i + 1)$ is dequeued, every single possible path of length $i$ has already been evaluated. Therefore, prob[i + 1, v] is mathematically guaranteed to contain the absolute maximum probability for reaching $v$ at that step, and it is safe to use it to compute the next layer.

The time and space complexity remains the same as before.

14-8 mage compression by seam carving

Available in the latest revision of the IM.

14-9 Breaking a string

Available in the latest revision of the IM.

14-10 Planning an investment strategy

a.

To prove that there is always an optimal strategy that puts all the money into a single investment each year, we can evaluate the mathematics of a split portfolio versus a single-investment portfolio, factoring in the flat fee structure. Let’s define an "epoch" as any continuous block of time from year $a$ to year $b$ where no switching occurs (meaning only the $f_1$ fee is paid each year). For this period, compute the cumulative rate of investment $i$ as $R_{i}^{(ab)}=\prod_{k=a}^b r_{ik}$. If $R_{max}^{(ab)}$ is the highest cumulative rate among all the investments over these years, then:

$$d \sum_{i=1}^n x_i R_i^{(ab)} \le d \cdot R_{max}^{(ab)},$$

where $d$ represents the amount of money and $x_i$ the fraction of this money put into investment $i$, such that $\sum_{i=1}^n x_i = 1$. So, even if a high $f_2$ fee forces a multi-year hold, identifying the single investment with the highest cumulative rate for that period and putting 100% of the money into it will always yield an equal or greater return than diversifying.

This means the entire 10-year strategy can be mathematically reduced to:

1. Choosing the optimal duration for each epoch.

2. Choosing the single best investment to hold during that epoch.

3. Paying the $f_2$ switching fee strictly at the boundaries between epochs.

This constitutes an existential proof of an optimal investment strategy that, in each year, puts all the money into a single investment.

b.

From part (a), we know that inside each epoch we should put all the money into a single investment with highest cumulative rate. Let $m[i, j]$ be the maximum amount of money we can have at the end of year $j$, given that our money is in investment $i$ for that year. To calculate the optimal value for the prefix problem $(1, j)$ ending in investment $i$, we only need to look at the independent, already-optimized subproblems from year $j-1$. The cut-and-paste argument clearly applies. Therefore,

$$m[i, j] = \max \left\{ (m[i, j-1] - f_1) \cdot r_{ij}, \left( \max_{k \neq i} \{m[k, j-1]\} - f_2 \right) \cdot r_{ij} \right\}.$$

c.

Investment-Plan(d, r, n, f1, f2)
1  let m[1 : n, 1 : 10] and prev[1 : n, 1 : 10] be new tables
2  
3  // Base Case: Year 1 (No fees applied yet)
4  for i = 1 to n
5      m[i, 1] = d * r[i, 1]
6      prev[i, 1] = NIL
7      
8  // DP Transitions: Year 2 through 10
9  for j = 2 to 10
10     for i = 1 to n
11         // Default option: Stick with the same investment
12         m[i, j] = (m[i, j - 1] - f1) * r[i, j]
13         prev[i, j] = i
14         
15         // Evaluate switching from every other investment
16         for k = 1 to n
17             if k != i
18                 switch_val = (m[k, j - 1] - f2) * r[i, j]
19                 if switch_val > m[i, j]
20                     m[i, j] = switch_val
21                     prev[i, j] = k
22 
23 // Find the absolute best outcome at the end of year 10
24 max_money = -∞
25 best_last_inv = NIL
26 for i = 1 to n
27     if m[i, 10] > max_money
28         max_money = m[i, 10]
29         best_last_inv = i
30 
31 // Reconstruct the path backwards
32 let strategy = a new empty list
33 curr_inv = best_last_inv
34 for j = 10 down to 1
35     prepend curr_inv to strategy
36     curr_inv = prev[curr_inv, j]
37 
38 return strategy, max_money

The running time is $\Theta(n^2)$ and the space complexity is $\Theta(n)$. This applies for a fixed 10-year period.

d.

In our previous proofs, the problem relied on monotonicity: having more total money at the end of year $j<10$ strictly meant we could generate more money at year 10. Once a $15,000 cap is introduced, capital is no longer just a single number—its distribution matters. If we aggressively maximize our money in year $j$ by pouring it all into one high-yield investment, we will hit the cap. To continue growing, we will be forced to split our money across multiple investments in year $j+1$, which triggers the potentially massive $f_2$ fee. To avoid that fee, a globally optimal strategy might require us to intentionally "underperform" in earlier years by splitting our money early, perfectly positioning our portfolio to ride high rates later without ever hitting a cap or paying a fee.

14-11 Inventory planning

Available in the latest revision of the IM.

14-12 Signing free-agent baseball players 🌟

This exercise is a variation of the famous knapsack problem.

Available in the latest revision of the IM.

The solution in the IM doesn't consider an important detail from the description. Namely, the problem explicitly states that every player signs for a multiple of $100,000; we can drastically optimize the space and time complexity by scaling the budget.

• Let $X = \lfloor X / 100,000 \rfloor$.

• For each player $p$, let $p.cost = p.cost / 100,000$.