動的プログラミングテーブル - 文字列を分割するための最小コストの検索

Question

特定の文字列処理言語は、文字列を2つに分割するプリミティブ操作 を提供します。この操作には元の文字列をコピーする が含まれているので、切り取りの位置に関係なく、長さnの文字列の場合はn時間単位で処理されます（ ）。今、 という文字列を多くの部分に分割したいとします。

ブレークの順序は、実行中の合計時間に影響します。 たとえば、添え字3,8、および 10の文字のあとに20文字の文字列（ の例 "abcdefghijklmnopqrst"）を分割して、 "abcd"、 "efghi"、 "jk"および " lmnopqrst "となります。 ブレークが左右に行われた場合、最初のブレークは20 単位の時間を、2番目のブレークは16単位の時間を、第3の ブレークは11単位の時間を費やして合計47ステップになります。 が右左の順序で行われる場合、最初のブレークは20単位の時間を要し、 の第2のブレークは11単位の時間を要し、第3のブレークは単位の時間を要し、合計でわずか40歩です。しかし、最適な 解は38です（カットの順序は10,3,8です）。

入力は、文字列の長さとカットインデックスを持つ昇順ソート配列です。私は、文字列を切る最小限のコストと、カットを実行する順序を見つけるために、動的プログラミングテーブルを設計する必要があります。

テーブル構造がどのように見えるかを特定できません（特定のセルは特定のサブ問題に対する答えである必要があり、他のエントリなどから計算可能である必要があります）。代わりに、私は文字列を壊すための最小コストを見つけるために再帰関数を書いた：iとjの間の（サブ）文字列に行わなければならないカットのインデックスはb0, b1, ..., bKです。

totalCost(i, j, {b0, b1, ..., bK}) = j - i + 1 + min { 
               totalCost(b0 + 1, j, {b1, b2, ..., bK}), 
    totalCost(i, b1, {b0     }) + totalCost(b1 + 1, j, {b2, b3, ..., bK}), 
    totalCost(i, b2, {b0, b1    }) + totalCost(b2 + 1, j, {b3, b4, ..., bK}), 
    .................................................................................... 
    totalCost(i, bK, {b0, b1, ..., b(k - 1)}) 
} if k + 1 (the number of cuts) > 1, 
j - i + 1 otherwise. 

テーブルの構造を理解してください、ありがとう！

Answer 1

たとえば、長さがn = 20の文字列があり、位置をcuts = [3, 8, 10]にする必要があります。まず最初に、2つの偽のカットを-1とn - 1（エッジの場合を避けるため）に追加しましょう。現在はcuts = [-1, 3, 8, 10, 19]です。テーブルMを記入しましょう。M[i, j]は、i番目とj番目の間のすべての改行を行うための最小時間単位です。私たちはルールで記入することができます：M[i, j] = (cuts[j] - cuts[i]) + min(M[i, k] + M[k, j]) where i < k < j。すべてのカットを作成する最小時間はセルM[0, len(cuts) - 1]になります。 Pythonの完全なコード：

# input 
n = 20 
cuts = [3, 8, 10] 
# add fake cuts 
cuts = [-1] + cuts + [n - 1] 
cuts_num = len(cuts) 
# init table with zeros 
table = [] 
for i in xrange(cuts_num): 
    table += [[0] * cuts_num] 
# fill table 
for diff in xrange(2, cuts_num): 
    for start in xrange(0, cuts_num - diff): 
     end = start + diff 
     table[start][end] = 1e9 
     for mid in xrange(start + 1, end): 
      table[start][end] = min(table[start][end], table[ 
            start][mid] + table[mid][end]) 
     table[start][end] += cuts[end] - cuts[start] 
# print result: 38 
print table[0][cuts_num - 1]