p'
with finger f'
?
 Subproblems: prefixes? suffixes? substrings? Suffixes are kind of fine. How toplay notes
n[i:]
.  Guess: Which finger to put on note
i
?  Recurrence:
dp[i] = min({
for f in fingers:
dp[i+1] + d(i, f, i+1, ?)
})
 Add more subproblems! how to play
notes[i:]
when using finger f
for notes[i]
.  What to guess? finger
g
for note (i+1)
dp[i][f] = min({
for g in fingers:
dp[i+1][g] + d[notes[i], f, notes[i+1], g]
}
for i reversed(range(n)):
for f in range(F): ...
 Original problem: we don't know what finger to use for
dp[0]
. So we can takea min
over all fingers. min([ dp[0][f] for f in range(F)])
§ guitar chords:
Generalize the notion of "finger" to "finger(F) + string(S)". This gives
us $O(N((F+S)^2)) = O(NF^2S^2)$. Multiple notes: notes[i] = list of F notes
for
a piano.
 state: we need to know about the assignment of fingers to notes (or no note).So that's $(N+1)^F$. Generalize the rest.
§ Tetris
We know the entire sequence of pieces that's going to fall. For each, we must
drop the piece from the top. Also, full rows don't clear.
The width of the board is small. The board is initially emoty.
Can you survive?
The subproblems are how to play suffixes of pieces[i:]
. We need to know
what the board looks like. If the board doesn't clear and we always drop from
the top, then all we need to know is the skyline.
1 ###
2 #
3####
4####
5####
 So we also store the board skyline. We have
h
different choices for eachcolumn. There are w
columns. So we have (h+1)^w
number of choices forskylines. Total number of subproblems is n.(h+1)^w
.  Guess: what do I do with piece
i
? I can rotate it 0, 1, 2, 3
times, and thewhere to drop it. I can guess where to drop the piece. This is 4w
choices 4
for rotation, w
for where we drop.
 Here the answer is a boolean: survive (1) or not (0). we want to survive, sowe can just use
max
on a boolean.
§ Super Mario Bros
Recall that in the original super mario bros, if something moves out of the
screen it's lost forever; We can't move back in the old mario. We're given
the level, and a small $w\times h$ screen. The configuration of the game is
everything on the screen! Total info is going to be $c^{wh}$ where c
is some
constant. We also need Mario's velocity, the score, and time. score can be S
big, time can be T big. The number of configurations is the product of all of
these. We also need to know how far to the right we have gone, which is another
W
. Draw a graph of all configurations, and then use DP
§ Lecture 10: Advanced DP by Srinivas
§ Longest palindromic sequence
Find palindrome inside longer word. Given a string X[1..n]
. Find longest
palindrome that is a subsequence.
character
c arac
answer will be greater than or equal to 1 in length because a single letter
is a palindrome.
turboventilator
r o t ator

L[i, j]
: length of longest palindromic subsequence in string xs[i:j]
where i<=j
.
def L(i, j):
if i > j: return 0
if i == j: return 1
if x[i] == x[j]:
return 2 + l(i+1, j1)
return max(L(i+1, j), L(i, j1))
 number of subpbroblems: $O(n^2)$. Time per subproblem assuming recursion is free: $O(1)$.Hence, total time is $O(n^2)$.
§ Optimal binary search trees
Find most balanced BST for a set of keys. We have weights for the keys, which
are search probabilities. Find a BST T (there are exponential number of BSTs)
that minimizes $\sum_i w_i (depth_T(k_i) + 1)$. Depth of root is 0. Depth
of a node is distance from the root. This minimizes expected search cost.
§ Enumeration
We have exponentially many trees.
§ Greedy soltution / Why doesn't greedy work?
Assume the keys are sorted.
Pick K[i]
in some greedy fashion (max.weight).
This immediately splits the set of keys into the left and right.
If we define e(i, j)
to be the cost of the optimal BST on keys k[i], ..., k[j]
.
greedy:

2w=10
1w=1 4w=9
3w=8
optimal:

3w=8
2w=10 4w=9
1w=1
§ DP
 Guess all possible root nodes. The greedy algorithm doesn't try to guess theroot node, that's the only difference.
 e(i, j): cost of tree with keys k: i <= k <= j
def e(i, j):
if i == j: return w[i]
return min([e(i, r1) + e(r+1, j) + w[r]
for k in range(i, j+1)])
The weights are going to change when we increase depth, so we actually need
to add all the weights from i
to j
! So we write:
 e(i, j): cost of tree with keys k: i <= k <= j
def e(i, j):
if i == j: return w[i]
return min([e(i, r1) + e(r+1, j) + weight(i, j)
for k in range(i, j+1)])
§ Alternating coins
Have a list of coins. We have an even number of coins.
Can only pick coins from the outside.
First player can always not lose in the game. What the first player does
is compute v[1] + v[3] + ... v[n1]
versus v[2] + v[4] + ...
which is even.
If the odd values win, the he picks v[1]
. P2 can pick v[2]
or v[n]
.
P1 can pick either v[3]
or v[n1]
depending on if P2 picked v[2]
or v[n]
.
 We now want to maximize the amount of money.
v(i, j) = max([ range is(i+1, j) with P2 + v[i],
range is (i, j1) with P2 + v[j] ])
If we have v(i+1, j)
subproblem with the opponent picking, we are guaranteed
that the opponent plays min(v(i+1, j1), v(i+2, j))
. So we can unfold this,
to get the full DP:
v(i, j) = max([ min(v(i+1, j1), v(i+2, j)) + v[i],
min(v(i, j1), v(i+1, j)) + v[j],
§ DP: All pairs shortest paths.