分割使用动态规划

Question

字符串假设你有一个函数quality(x)返回字母x序列的质量。给定一个字符串，如“howareyoutoday，”什么是最有效的方式来确定分割是“你今天怎么”（即品质（如何）+质量（是）+质量（你）+质量（今天）是最高质量可能）？

我在想，我们可以有类似如下：

A[0] = h, A[1] = o, ..., A[n] = y 
Q[0] = quality(A[0]), Q[1] = quality(A[0]A[1]), ..., Q[n] = quality(A[0]...A[n]) 

我们确定的分割，我们发现最大{Q [0]，...，Q [N]}，它会返回一些Q [我]（第一个空间在此之后）。然后，我们找到返回另一个Q [i]的最大{Q [i + 1]，... Q [n]}（等于此之后的第二个空间）等，直到最大返回Q [n]。

我有两个问题：这是否方法使用动态编程？在我看来，它确实如此，因为我们用最初的问题的子问题构建了初始Q值。此外，这是一个最佳的解决方案？据我了解，最坏的情况将是为O（n^2），最大时返回Q [0]，那么Q [1]，然后Q [2]等

Answer 1

您可以使用动态编程这将是如果你可以使用缓存的子问题结果。例如，如果质量（A [0] A [1]）是质量（A [0]）和质量（A [1]）的函数（例如质量（A [0] A [1]）=质量A [0]）+ quality（A [1]）），那么您可以通过缓存子问题的结果来获益;如果质量（A [0] A [1]）与质量（A [0]）和质量（A [1]）无关，则缓存子问题的结果不会使您受益，使用动态编程。

您的算法的最坏情况是O（n^2）。您可能能够使用潜在的次优O（n）解决方案：测试质量（A [0]），质量（A [0] A [1]），质量（A [0] A [ 1] A [2]）等等;如果质量（A [0] A [1]）>质量（A [0] A [1] A [2]）在当前解决方案的质量低于先前解决方案的质量时停止， A [0] A [1]并开始搜索A [2]中的下一个单词。您可以通过增加前瞻来以更大的常数因子为代价来提高算法的质量;如果质量（A [0] A [1]）>质量（A [0] A [1]），则刚刚描述的算法具有前瞻性（1），而先行（2）算法将在A [0] 1] A [2]）和质量（A [0] A [1]）>质量（A [0] A [1] A [2] A [3]）。制定这是一个DP问题

Answer 2

的一种方法是计算一个函数f（I）：

f(i) = The highest sum of quality scores achievable on the first i characters. 

我们注意的是，最后一段必须在定位端的i-1，它可以开始在它之前的任何位置，回到位置0（假设我们从0开始编号）。我们称这段j的起始位置为;我们需要尝试j的所有可能值，并找到最好的值。我们应该把这个最后的部分A [j] .. A [i-1]与？使用最佳的解决方案，无论剩余在其左边，这通常由f（j）给出。所以我们得到：

f(i) = max { f(j) + quality(A[j]..A[i-1]) } over all 0 <= j <= i. 

其中f（0）= 0作为边界情况。

F（N + 1）将计算在二次时间和使用线性内存要求整个字符串的最佳得分。要真正计算出单词中断的位置应该得到这个分数，您需要从f（n + 1）向后走，确定哪个j值使其达到最大值（可能有几个;在这种情况下， ）。继续重复这个操作直到你得到j = 0（或者你可以在计算f（）时将这些j的“最大化”值存储在一个单独的数组中，这个数组通常被称为“pred []”。）

[编辑]

上面是解决该问题的递归。它会正确解决，但非常缓慢的大n。所有DP算法都可以用这种方式表述，但要将它从简单的递归转换为DP算法，您需要输入memoize它，或者找出如何从中自下而上填充表格填充迭代算法。递归的记忆是微不足道的：只要函数计算出我的新值的答案，就存储这个答案（这里是一个大小为n + 1的数组），下次使用它时要求f（i）的特定值。自下而上的DP涉及计算可填充表的顺序，以便满足所有依赖关系。这可以是（恒定的因素）更快，但有时难以做到。