0

这基本上是重复的：

如何将字符串拆分为单词。例如：“stringintowords”->“String Into Words”？

neverthelees，我在使用中使用了一个函数，例如：public int Word(x) {code}，对于字符串 x，它将返回一个整数（+ve 或 -ve），并且该整数将指示分区对于特定单词的好坏程度. 我应该返回给出最大数量的组合。

我想为此做的是创建一个 table(i,j) ，其中 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
然后第一条路径的总和 > 2nd

EDIT2：我希望每个人都知道，经过长时间的工作，我已经回答了这个问题，不要介意没有得到解决方案，我想自己得到它总是最好的：P

干杯！：）

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+1+1= 7 (对角线向下 i=j) 这意味着 talbe 不正确...

如果我只能存储上一个最佳输入的位置，这可能会起作用。（我再次认为）

于 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 函数会告诉您每个位置的最大值。如果您迭代子字符串大小、变量 j 并不重要，因为 Word 不使用 j。

如果我对这些假设有误，请纠正我。

于 2010-12-04T23:59:48.500 回答