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

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) 开始填充表格 - 只需考虑它需要哪些单元格:您尚未填充的单元格(也如果你能做到，那么你可以一步计算出最终答案)。

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