Correctness

Write: g: s to stand for all elements of the set of segmentations of a string s.

M(s) is the maximum probability of a segmentation of string s.

• $M(s) = \max_{g: s} \prod_k D[g[k]]$
• $= \max_{i=1}^{\vert s\vert} \max_{g: s[(i+1)..n]} D[s[1..i]] \prod_k D[g[k]]$
• $= \max_{i=1}^{\vert s\vert} D[s[1..i]] \max_{g: s[(i+1)..n]} \prod_k D[g[k]]$
• $= \max_{i=1}^{\vert s\vert} D[s[1..i]] M(s[(i+1)..n])$

Can implement this directly to get a correct but exponential-time algorithm. Need to reuse results instead of recomputing over and over.

Recurrence: T(1) = 1, $T(n) = n + \sum_{i = 1}^{n-1} T(i)$.