algorithm - DP 左上角与右下角表格填充。什么时候使用哪个？

Question

有很多问题需要从左上角(例如:编辑距离)和从右下角开始(例如:回文子字符串)填充表格。 对于何时使用哪个有任何直观的解释吗？ 引用:
http://www.geeksforgeeks.org/dynamic-programming-set-5-edit-distance/
https://leetcode.com/problems/palindromic-substrings/discuss/

Answer 1

表本身的方向没有任何区别，在简单的索引转换下它是同构的。也就是说，您可以通过从该维度的大小中减去该索引来轻松地在任何维度上翻转表格。这没有任何区别，您可以说算法甚至不“知道”您正在这样做，您甚至可以创建一个类似表格的对象来抽象该转换，以便代码看起来完全相同，但是在深处有一张 table 在相反的方向被填满。

解决子问题的顺序很重要，它必须遵循依赖结构。找到解决子问题的适当顺序实际上是“将递归变成DP” list 中的重要一步，它经常被忽视，因为通常有一些琐碎的顺序可以工作，您甚至不需要考虑。但例如，以下是斐波那契递归的结构，由维基百科提供:

您可以在这里看到(并且从递归定义中也可以立即明显看出)具有某些参数的调用仅依赖于具有较小参数的调用。因此，按照从最低参数到最高参数的顺序填充表格是有效的顺序，这保证了当需要表格中的单元格时，它已经被计算过。 (通常这会进一步优化以仅保留前两项而不是所有前面的项目，但这不是重点)

事情并不总是那么简单，尤其是在更高的维度中，但在您的编辑距离示例中:(src:geeksforgeeks.org)

您可以看到每个 eD(x,y) 仅取决于 eD(x-dx,y-dy)，其中 dx 和 dy 为 0 或 1，而不是两者 0，这是满足的通过许多个订单，例如(不限于):

• 按 (y,x) 的字典顺序(在他们的答案中呈现)
• 按 (x,y) 字典顺序排列(只需反转内循环和外循环)
• 反对角线
• 从 0,0 开始，将填充单元格的矩形向下延伸 1 步，然后向右、再次向下，依此类推
• 将其扩展 k 步
• 通过向下、然后向右等步骤缩小空单元格的矩形
• 以 0,0 为中心的半径扩大的四分之一圆

您需要保留的是，当计算 eD(a,b) 时，它所需的一切都已计算完毕。这留下了很大的自由度，您甚至可以取出左侧和顶部已填充单元格的所有空单元格，然后随机选择一个进行填充。然而，一个绝对不能解决这个问题的顺序是填充从 (m,n) 开始的表格 - 只需想想它需要哪些单元格:您尚未填充的单元格(也可以如果你能做到，那么你就可以一步计算出最终答案)。

就依赖图而言，任何拓扑顺序都可以。