1

我正在阅读有关动态编程的问题。问题如下：

将长度为 n 的字符串分解为一系列有效单词。假设有一个数据结构可以告诉您字符串在恒定时间内是否是有效单词。

我以某种方式解决了它，但后来我读到的解决方案如下：

创建一个表 T[N]，如果子字符串 [0...i] 可以分解为一系列有效单词，则 T[i] 为真。如果存在 aj，则 T[i] 为真，0<=j<=k-1 其中 T[j] 为真且 S(j,k) 是有效词

这是 DP 的经典公式，但它不是错的吗？不应该是：

如果存在 aj，则 T[i] 为真，0<=j<=k-1 其中 T[j] 为真且 S( j+1 ,k) 是有效词或 S(0,i) 是有效词字？

否则，我看不到如何构建表格，例如对于字符串： 如果我们不考虑这是一个单词并且下一个序列是j = 2 ，itsthe我们将永远不会有。 我是对的这里？但是我们如何才能找到实际的单词呢？ 我为理解而制作的示例代码（从java中 返回子字符串）：T[2] = trueitstheS(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]长度true。让我们调用这个数组L[i]

如果存在 aj，则 T[i] 为真，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 回答