algorithm - 从最优子结构到实际算法

Question

随着我对动态规划的了解越来越多，我发现在给定情况下形成最优子结构的概念越来越容易。例如，通过找到乘以矩阵链的最佳顺序，我了解到(抱歉冗长；它帮助了我)可以找到计算 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] 的最大值(如果我混合任何东西......)

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

谢谢!

Answer 1

Do I basically just run loops to tabulate everything, and then essentially 'choose' what is needed from the table?

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

因此，一旦您创建了内存数组/矩阵等，您通常要做的就是在该数组中设置基本案例值，然后让算法运行。结束条件通常是当您到达数组中的正确点时，或者当没有任何东西需要计算时(此时您从数组/矩阵等中“选择”您需要的东西)

我希望这足够具体有用。