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