> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-iv-advanced-design-and-analysis-techniques/14.-dynamic-programming.md). # 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.** {% hint style="danger" %} 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. {% endhint %} ### 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 {% hint style="danger" %} The IM solution is broken, as it doesn't select $$k$$ to minimize the quantity $$p\_{i-1} p\_k p\_j$$. {% endhint %} 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.** {% hint style="warning" %} The code in the IM lacks the base cases (when $$i=0 \lor j=0$$ then $$c\_{ij}=0$$). {% endhint %} ### 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](https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf). 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\ 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.** {% hint style="warning" %} 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. {% endhint %} ### 14-4 Printing neatly **Available in the latest revision of the IM.** {% hint style="warning" %} 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`. {% endhint %} ### 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 🌟 {% hint style="success" %} This exercise is a variation of the famous [knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem). {% endhint %} **Available in the latest revision of the IM.** {% hint style="warning" %} 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$$. {% endhint %}