常用算法路径遍历类型的求解方法

Question

• 给定一个矩阵，我们必须从每一行中选择一个值，这样所选择的总价值成本是最小的。
• 现在的问题是，如果在前面的行中选择了列"J“，则不能选择”I“第四行中的列"0”到"J“。
• 也就是说，我们只是在向右移动，我们不能在向下移动时向左移动。

我能想到的是，如果我们从最后一行开始，然后向上移动，那么我们必须寻找所有可能的组合，即时间复杂性O(2^n)，但是是否有另一种有效的方法来解决这类问题呢？

Answer 1

这是最短路径问题的一个变体，您的图形是：

G = (V,E)
V = { (x,y) | for each cell in the matrix } U { (-1,-1) } //assuming 0 based matrix
E = { ((x1,y),(x2,y+1)) | x1 < x2 } // or x1<=x2 - depends if you can go straight down
w((x1,y1),(x2,y2)) = value(x2,y2) //weight function

现在，这是一个图(实际上是有向无圈图)，您可以将最短路径算法从单个源(-1,-1)应用到格式(x,n-1)的多个目标上，其中n是行总数。解决这个问题的一个算法是迪克斯特拉算法。

在理解了这是一个DAG之后，我们甚至可以使用直接的DP解决方案来进一步优化它(这实际上模拟了最短路径算法，但利用了DAG特性)：

D(-1,-1) = 0
D(x,y) = min { D(x', y-1) | for each x'>x }  U {infinity} + value(x,y)

最后的答案将是min{ D(x,n-1) | for all values of x}。

此解决方案在O(n*m*m)中运行，其中n是行数，m是列数。