Maximum Probability Segmentation

Recall how we developed an algorithm for this.

• We began with a recursive formulation: The best way to break up a sequence is the best combination of a first word with the best way to break up the remainder of the sequence.
• Then, we noticed that implementing this directly recursively would result in lots of wasted work.
• So, we decided to ``cache'' the results of our work and compute answers in reverse order to fill in the table. That way, whenever we need the solution to a subproblem, it's already in our table.
• Actually, a lot like solving problems on a DAG (since you can write the computational dependencies as a graph and work in reverse topological order).
• Running time was O(n²), since each of the n table entries takes O(n) to fill in.