0

これは基本的に次の複製です。

文字列を単語に分割する方法。例: "stringintowords" -> "文字列を単語に変換"?

それにもかかわらず、私は次のような関数を使用しています: public int Word(x) {code}、文字列 x の場合、整数 (+ve または -ve) を返します。その整数は、特定の単語に対するパーティション分割の良し悪しを示します。 . 最大数を与える組み合わせを返す必要があります。

このために私が考えたのは、 i と j が単語の長さである table(i,j) を作成し、次のように表を tern に記入することです。

for i = 1 to n
   for j=i to n do 
      word(subset of x i to j)

それにもかかわらず、一体どのようにして最適解を取得できるのでしょうか (再帰的な方法で?)

助けていただければ幸いです。

編集: 最適なパスは、word(x) 関数の合計が最も高いパスです。つまり
、 path(1,3)=10 、 (3,6)=20 、 (6,7)=1 、および
パス (1,1)=0 、(2,5)=12、(5,7)=-1
の場合、1 番目のパスの合計 > 2 番目

EDIT2：この質問は、長時間の作業の後に私が回答したことをすべての人に知ってもらいたいのですが、解決策が得られないことを気にしないでください。

乾杯！：）

4

2 に答える 2

0

わかりました、例を挙げましょう：

word thetree


         1  2   3  4  5  6  7 ( ending index)

start 1  1  -1  2 -1 -1 -1 -1
      2  0  1  -1  -1 -1 -1 -1
      3  0  0   1  0  0  0  0
      4  0  0   0  1  0  0  4
      5  0  0   0  0  1  0  0
      6  0  0   0  0  0  1  0  
      7  0  0   0  0  0  0  1

この解決策をよく考えてください。次に、各列を個別に保存すると、列番号 3 で 2 が得られ、7 で 4 が得られ、合計で 6 になりますが、各文字を個別に取得すると、次のようになります。 1+1+1+1+1= 7 (斜め下 i=j) は、タルベが正しくないことを意味します...

これは、前のエントリの位置を保存するだけでうまくいく可能性があります.(もう一度思います)

于 2010-12-05T01:18:37.993 に答える
0

サム あなたはこう言っています：

文字列内の位置で満たされたテーブルがあり、長さ j の部分文字列がある場合は各セルのブール値があります。

例：

                    |       Positions of the example:
                    |            "xdeafcatmonologue"
 -------------------|-------------01234567890123476----------------
length of substring |                              
        1           |             11111111111111111     
        2           |             ------2----------
        3           |             -----3------3----
        4           |             -4--------------- 
        5           |             -----------------
        6           |             -----------------
        7           |             -----------------
        8           |             -----------------
        9           |             --------9--------
                    |              

      final         |             -4---3--9---3----

ダッシュは技術的にゼロであり、数字は潜在的なものであり、これが作成するテーブルです.

Word 関数は各位置の最大値を通知するため、各位置の最大値のみを格納する場合は、はるかに小さなテーブルを作成できます。Word は j を使用しないため、部分文字列のサイズ (変数 j) を反復処理しても問題ありません。

これらの仮定のいずれかで間違っている場合は、修正してください。

于 2010-12-04T23:59:48.500 に答える