1

随着我对动态规划的理解，我发现在给定情况下开发最优子结构的概念越来越容易。例如，在找到乘以矩阵链的最佳顺序时，我知道（对不起，冗长；它帮助了我）计算 Ai * Ai+1 * ... * Aj 所需的最小乘法数可以找到通过找到 i 和 j 之间的拆分/括号放置点 k，它最小化 Ai*... Ak 和 Ak+1 ...*Aj 所需的乘法之和，加上实际尺寸带来的成本。换句话说，M(i,j) = mink(M(i,k) + M(k+1,j) + di-1dkdj)。

同样，在找到字符串的最长回文子串时，最佳子结构是索引 i 和 j 之间的最大长度回文的长度 l[i,j] 并且输入数组是 2 + l[i+1, j -1]，当 i 和 j 处的元素相同并因此可以相加时，否则为 l[i+1, j], l[i, j-1] 的最大值（如果我混淆了任何内容，请纠正我...)

但是，在任何情况下，我如何将其转换为算法来找到理想序列的长度，例如上面的，甚至是它的内容？我是否基本上只是运行循环将所有内容制成表格，然后基本上“选择”表格中需要的内容？使用矩阵链，这似乎正是要做什么，但对于回文，我对如何构建循环有点困惑。

谢谢！

4

1 回答 1

1

我是否基本上只是运行循环将所有内容制成表格，然后基本上“选择”表格中需要的内容？

简而言之，是的。动态编程依赖于两件事：使原始问题更小（在您的问题中有很好的描述）和基本情况：那些（几乎总是很小）解决方案显而易见的情况，不再需要将问题划分为子问题。例如，在您的矩阵乘法示例中，一旦子问题减少到 2 个矩阵，您就不再有选择：您必须按原样将它们相乘。在您的回文示例中，我会选择长度为 1 的子串的基本情况，这显然是回文。

因此，一旦您创建了记忆数组/矩阵等，您通常所做的就是在该数组中设置基本情况值，然后让算法运行。结束条件通常是当您到达数组中的正确点时，或者当没有什么可以计算时（此时您从数组/矩阵等中“选择”您需要的内容）

我希望这足够具体以至于有用。

于 2012-09-28T20:51:41.427 回答