正在寻找动态规划解决方案

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. 第一阶段计算的查找表。 中号是任何字嵌入子我 ... Ĵ的最佳性价比。 W是与该成本有关的词。 ø（Ñ MW）（Ñ =输入长度，瓦特 =最大字长，和米 =单词计数）

2. 第二阶段发现的最佳字为每个位置。 大号是最好的总成本至位置我。 C是与该成本相关的最后一个词的开始位置。 ø（Ñ ）

3. 最后一个阶段组装最终的字符串。 R是与输入字符串匹配时收到最低成本的单词列表。 ø（Ñ）。

第一阶段是最昂贵的。应该有可能削减一个数量级，但我不知道如何。你也可以将它与阶段2结合起来，但是你从中获益不多。