Lecture 10: Dynamic Programming: Advanced DP

What this lecture covers

This lecture works through three dynamic programming problems of increasing difficulty, revisiting the standard DP recipe (define subproblems, write a recurrence, memoize or iterate, then recover the actual solution) and showing where it needs new ideas. It starts with a review-level problem, longest palindromic subsequence, then moves to optimal binary search trees, where a natural greedy heuristic fails and has to be replaced by trying every possible root. It closes with a two-player coin game, where the recurrence must explicitly model an adversary's best response.

After watching, you should be able to write the DP recurrence for longest palindromic subsequence and argue its complexity, explain why picking the highest-weight key as the BST root is not always optimal, construct the optimal-BST recurrence by "guessing" every possible root, and set up a minimax-style DP recurrence for a two-player game where you must account for the opponent playing optimally against you.

Key ideas

• DP recipe recap: identify optimal substructure, write a recurrence connecting a problem to its subproblems, compute the optimal value via recursive memoization or bottom-up iteration, then separately reconstruct the actual solution (not just its value) via backtracking.
• Longest palindromic subsequence: for L(i, j), if i == j the answer is 1; if x[i] == x[j] the answer extends the inner subsequence by 2 (or is 2 directly when adjacent); otherwise it is the max of dropping the i-th or the j-th character; this gives Theta(n^2) subproblems, each Theta(1) to combine, for Theta(n^2) total time with memoization (versus exponential time without it).
• Optimal binary search trees (BSTs): given sorted keys with weights (interpretable as search probabilities), find the BST minimizing the sum, over all keys, of weight * (depth + 1), which corresponds to minimizing expected search cost.
• Why greedy fails for optimal BSTs: always picking the highest-weight remaining key as the root (recursively) seems reasonable but can produce a worse tree than an alternative choice; a four-key counterexample shows a lower-cost tree exists that greedy does not find.
• "Guess" as a DP technique: when the optimal root is unknown, the DP tries every possible key as the root (a linear number of guesses) and takes the minimum cost result, unlike greedy, which commits to one guess.
• Optimal-BST recurrence: E(i, i) = w_i; otherwise E(i, j) = min over r in [i, j] of E(i, r-1) + E(r+1, j) + W(i, j), where W(i, j) is the sum of weights from i to j, added once per level of recursion to account for increasing depth; this gives Theta(n^2) subproblems and Theta(n^2) total time.
• Alternating coins game: two players alternately take a coin from either end of a row of n (even) coins, trying to maximize their own total; the first player can always guarantee at least a tie by fixing a parity (odd or even positions) in advance, but maximizing total winnings against an optimal opponent requires DP.
• Modeling the opponent with a min: because the mover only controls their own choice, not what the opponent leaves behind, the recurrence must assume the opponent plays to minimize the mover's future value, giving V(i, j) = max(v_i + min(V(i+2, j), V(i+1, j-1)), v_j + min(V(i+1, j-1), V(i, j-2))).

Walkthrough

Longest palindromic subsequence (6:03)

Given a string x[1..n], the goal is the longest subsequence (not necessarily contiguous) that reads the same forwards and backwards. The lecture defines L(i, j) as the length of the longest palindromic subsequence of x[i..j], with the base case L(i, i) = 1. If the endpoints match, L(i, j) = 2 when adjacent or 2 + L(i+1, j-1) otherwise; if they don't match, L(i, j) = max(L(i+1, j), L(i, j-1)). Without memoization this recurrence is exponential (T(n) = 2*T(n-1)); adding a 2D cache brings it to Theta(n^2) subproblems at Theta(1) work each. The lecture notes that recovering the actual palindrome (not just its length) requires additional backtracking through the memo table.

Optimal binary search trees: problem setup (22:30)

Given sorted keys k_1 < ... < k_n with weights w_1, ..., w_n (interpreted as search probabilities, as in a dictionary where common words should be found faster), the goal is a BST minimizing sum_i w_i * (depth(k_i) + 1), which corresponds to minimizing expected search cost. Unlike balanced BSTs, this optimality criterion depends entirely on the weights, and there are exponentially many candidate trees.

Why the greedy root choice fails (34:48)

A natural heuristic picks the highest-weight key as the root, recursively splitting the remaining keys into left and right subtrees by key order. The lecture works a four-key counterexample (weights making key 2 the heaviest) where this greedy choice yields a tree with cost 54, while a different root choice yields cost 49, proving greedy is not optimal for this problem, unlike the earlier weighted interval scheduling case where a similar greedy idea had worked.

The optimal-BST recurrence (44:58)

Since the optimal root is unknown, the DP "guesses" every possible key r in [i, j] as the root of the subtree spanning keys i through j, recursively solving for the left part E(i, r-1) and right part E(r+1, j), and adding W(i, j), the sum of all weights in the range, once per level to account for the depth increment at every node below the current root. The base case is E(i, i) = w_i. This yields Theta(n^2) subproblems, each combining in Theta(1) after the linear-time guess loop is accounted for across the whole table, giving Theta(n^2) total time (or Theta(n^3) naively summing the guess loop per subproblem, refined with prefix sums for W(i,j)).

The alternating coins game and a non-DP trick (54:09)

In this game, two players alternately remove a coin from either end of a row of n (even) coins, keeping its value; the goal is to maximize your own total. The lecture demonstrates with volunteers that going first guarantees at least a tie: precompute the sum of odd-position coins and the sum of even-position coins, then always pick whichever parity is larger, since as first player you can always keep taking from that parity regardless of what the opponent does. This is not itself a DP, since it only requires summing two totals, but it does not maximize winnings when the two parity sums are close or you want the absolute best outcome.

DP for the maximizing coin strategy (1:03:17)

To find the strategy that maximizes total winnings while still being guaranteed a win, the lecture defines V(i, j) as the maximum value definitely achievable on your turn when only coins i through j remain. Base cases: V(i, i) = v_i, and V(i, i+1) = max(v_i, v_{i+1}). For the general case, the mover chooses v_i or v_j, but the resulting subproblem is what the opponent sees next, not what the mover controls. Because the opponent then picks whichever of the two remaining choices is worst for the mover, the recurrence takes a min over the opponent's options nested inside the mover's max: V(i, j) = max(v_i + min(V(i+2, j), V(i+1, j-1)), v_j + min(V(i+1, j-1), V(i, j-2))). This gives Theta(n^2) subproblems at Theta(1) work each, for Theta(n^2) total time.

Before you watch

• Be comfortable with the basic dynamic programming pattern (subproblems, recurrence, memoization) as covered in an introductory algorithms course.
• Recall the weighted interval scheduling problem from earlier in the course, since the optimal-BST discussion contrasts it with a case where a similar greedy strategy fails.
• Review the general DP complexity formula, number of subproblems times time per subproblem, used to analyze all three examples here.

Check your understanding

1. Write out the recurrence for longest palindromic subsequence and explain why memoization changes its complexity from exponential to Theta(n^2).
2. Describe a concrete example (or the one given in the lecture) where always choosing the highest-weight key as the BST root produces a suboptimal tree.
3. In the optimal-BST recurrence, why is the weight sum W(i, j) added once at every level of recursion rather than only at the top?
4. Explain the "guess everything" technique in DP: why does trying every possible root still keep the algorithm polynomial?
5. In the coins game DP, why does the recurrence take a min over the opponent's choices nested inside a max over the player's choices?