# Dynamic programming on strings

(JE5.8) A string is *palindromic* if is exactly the same as its
reversal, e.g. DEED, RACECAR, MURDEREDRUM. Describe and analyze an
algorithm to find the *length* of the longest palindromic subsequence
in a given string For example, the longest palindromic subsequence of
MAHDYNAMICPROGRAMZLETMESHOWYOUTHEM is MHYMRORMYHM, so given that
string as input, your algorithm should output the number 11.

# Dynamic Programming on graphs

Based on an exercise from Jeff Erickson.

Let `G = (V, E)`

be a directed graph with weighted edges; edge weights could be positive, negative,
or zero.

Describe an algorithm that constructs a directed graph

`H = (V' , E' )`

with weighted edges, where`V' = V ∖ {v}`

, and the shortest-path distance between any two nodes in`H`

is equal to the shortest-path distance between the same two nodes in`G`

, in`O(|V|²)`

time.Now suppose you know all shortest-path distances in

`H`

. Describe an algorithm to compute the shortest-path distances from`v`

to every other node, and from every other node to`v`

, in the original graph`G`

, in`O(|V|²)`

time.Combine the above results into an all-pairs shortest path algorithm that runs in

`O(|V|³)`

time. (The resulting algorithm is not the same as Floyd-Warshall!)