1

動的計画法に関する問題を読んでいます。問題は次のとおりです。

長さnの文字列を有効な単語のシーケンスに分割します。文字列が一定時間内に有効な単語であるかどうかを示すデータ構造があると想定します。

私はそれを私の方法で解決しましたが、私が読んだ解決策は次のとおりでした：

サブストリング[0...i]を有効な単語のシーケンスに分割できる場合、T[i]が真であることを示すテーブルT[N]を作成します。T [i]は、aj、0 <= j <= k-1が存在する場合に真になります。ここで、T [j]は真であり、S（j、k）は有効な単語です。

これはDPの古典的な定式化ですが、間違っていませんか？すべきではありません：

T [i]は、aj、0 <= j <= k-1が存在する場合に真になります。ここで、T [j]は真であり、S（j + 1、k）は有効な単語であるか、S（0、i）は有効です。単語？

そうでなければ、たとえば文字列の場合、テーブルがどのように構築される かわかりitstheません。それが単語であり、次のシーケンスがj = 2の場合 をT[2] = true考慮しないと、テーブルが作成されません。ここ？しかし、どうすれば実際の単語を見つけることができますか？ 私が理解するために作成したサンプルコード（Java のサブストリングを返します）：itstheS(2+1, N)

s.substring(i,j)i including j-1

int i = 0  
for(; i < s.length(); i++){  
   for(int j = 0; j > i; j++){  
       if(T[j] && dictionary.contains(s.substring(j + 1, i)){  
             T[i] = true;
             break;  
       }  
    }  
    if(dictionary.contains(s.substring(0, i + 1)){  
         T[i] = true;  
    }  
}
4

2 に答える 2

1

あなたはすべてのあなたの訂正において正しいです。

実際の単語を再構築する場合は、に設定t[i]した最後の単語の長さを示すテーブル配列をもう1つ追加しtrueます。この配列を呼び出しましょうL[i]

T [i]は、aj、0 <= j <= k-1が存在する場合に真になります。ここで、T [j]は真であり、S（j + 1、k）は有効な単語であるか、S（0、i）は有効です。語？前者の場合L[i] = j、後者で設定します- L[i] = i。

次に、再帰する必要がある終わりを追加します。L[n]ここnで、は指定された文字列の全長です。

于 2013-01-05T14:47:55.880 に答える
0

特にサブシーケンスを選択する場合は、表記の意味によって異なります。角かっこと丸かっこ「substring[0... i]」と「S（j + 1、k）」を組み合わせます。常に左側の人差し指を含め、右側の人差し指は含めないことをお勧めします。これは、左側に角括弧を使用し、右側に丸括弧を使用することで明示される場合があります：S [0 ... i）。

そうすれば、元の言い回しはほぼ正しいです。iとkの間には多少の混乱がありますが、これは同じであると思います。また、i=0の場合は正しく処理されません。（関連する注意点として、n = 0（空の文字列）の場合も、変更によって正しく処理されない可能性があると思います。）

Create a table T[N] which says that T[i] is true if the substring S[0...i)
can be broken into a sequence of valid words. T[i] is true iff i = 0 OR
(there exists a j, 0<=j<i, where T[j] is true AND S[j...i) is a valid word).
于 2013-01-05T15:43:12.917 に答える