В поисках решения для динамического программирования

Question

У меня следующая проблема:

Дана строка (без пробелов). И у меня также есть функция стоимости, которая возвращает стоимость строки (построена путем добавления оценочной стоимости каждого слова в строке). На самом деле он использует словарь и оценивает расстояние редактирования.

В моей программе необходимо вставить пробелы (как можно меньше), чтобы получить оптимальные глобальные затраты.

Я хочу необработанный алгоритм, оптимизации пойдут дальше.

Пример:

errorfreesampletext -> образец текста без ошибок
scchawesomeness -> такая удивительность

Answer 1

Я думаю, что это должно работать.

dp[i] = minimum cost if we consider only the first i characters

for i = 1 to n do
  dp[i] = cost(a[1, i]) // take sequence [1, i] without splitting it
  for k = 1 to i - 1 do
    dp[i] = min(dp[i], dp[k] + cost(a[k + 1, i])) // see if it's worth splitting 
                                                  // sequence [1, i] into
                                                  // [1, k] and [k + 1, i]

Answer 2

Вот алгоритм.Вероятно, он не самый эффективный, но самый лучший, который я мог придумать.

Input:
   A string of length n
   A list of words
Create a lookup table:
   Create a grid M of n x n slots. (1..n, 1..n)
   Create a grid W of n x n slots. (1..n, 1..n)
   For each starting position i in 1..n:
      For each ending position j in i..n:
         For each word w:
            Find the edit distance d between w and substring (i..j)
            If d is less than M[i,j]:
               Set M[i,j] to d
               Set W[i,j] to w
Find the best words for each position:
   Create a list L of (n+1) slots. (0..n)
   Create a list C of (n+1) slots. (0..n)
   Set L[0] to 0
   For each ending position i in 1..n:
      Set L[i] to infinity
      For each starting position j in 0..i-1:
         If L[j] + M[i,j] is less than L[i]:
            Set L[i] to L[j] + M[i,j]
            Set C[i] to j
Create the final result string:
   Create a list R
   Let i be the length of the input (n)
   Repeat while i > 0:
      Let j be C[i]
      Prepend W[j,i] to R
      Set i to j-1
   Return R

Этот алгоритм разбит на три этапа:

1. Первый этапвычисляет таблицу соответствия. M - лучшая стоимость вложения любого слова в подстроку i .. j . W - это слово, связанное с этой стоимостью. O ( n ³ мВт ) ( n = длина входа, w =максимальная длина слова и m = количество слов)

2. Второй этап находит лучшие слова для каждой позиции. L - лучшая общая стоимость до позиции i . C - начальная позиция последнего слова, связанного с этой стоимостью. O ( n ² )

3. На последнем этапе выполняется сборка последней строки. R - список слов, который получает наименьшую стоимость при сопоставлении с входной строкой. O ( n ).

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