Given a sequence of n characters, we need to decide where to put the spaces so that we get a sequence of valid words out.
How many different ways can we insert spaces?
On the other hand, how many possible words are in there?
If there are multiple ways to do this, which should we prefer?
We'll work up to a probabilistic model: choose the segmentation that gives us the most likely sequence of words.