正在尋找動態規劃解決方案

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結合起來，但是你從中獲益不多。