Разделить строку на строку допустимых слов с помощью динамического программирования

Мне нужно найти алгоритм динамического программирования для решения этой проблемы. Я пытался, но не мог понять. Проблема заключается в следующем:

Вам дается строка из n символов s [1 ... n], которая, по вашему мнению, является поврежденным текстовым документом, в котором исчезла вся пунктуация (так что это выглядит примерно как «это было лучше всего. .. "). Вы хотите восстановить документ, используя словарь, который доступен в виде логической функции dict (*), так что для любой строки w dict (w) имеет значение 1, если w - допустимое слово, а в противном случае имеет значение 0.

1. Приведите алгоритм динамического программирования, который определяет, может ли строка s [*] быть восстановлена ​​как последовательность допустимых слов. Время выполнения должно быть не более O (n ^ 2), предполагая, что каждый вызов dict занимает единицу времени.
2. В случае, если строка действительна, заставьте ваш алгоритм выводить соответствующую последовательность слов.