打印动态规划解决方案中遍历的路径

Question

问题很简单：在典型的动态规划解中，如何打印最终解计算过程中遍历的实际状态？

让我试着用一个例子来解释我到底需要什么-

假设，我们有一个 DP 问题的解决方案，其中每个状态都有二维，即解决方案中的状态看起来像 (i,j)。现在，我们有一个 起始状态 (0,0) 和一些 最终状态 ：(i,n)，其中 i 变化从 0 到 n。

因此，典型的解决方案如下：

Start from a starting state: in this case -> (0,0)
Move to the next state based on some computation: suppose from (0,0), we could go to (1,0), (1,1) or (1,2).
.
.
Keep on traversing until we reach one of the end states: in this case (i,n), for any i.

现在，我需要打印此解决方案中遍历的路径。基本上，如果我能找出我从哪个状态到达 最终状态 ，我就可以使用该逻辑返回到 起始状态 ，因此打印路径。

P.S.: 如果问题太明显，我们深表歉意。

Answer 1

您可以在计算期间显式存储此信息。也就是说，除了 DP(i, j) 之外，您还可以保存 PARENT(i, j)，它表示我们从中获得 (i, j) 结果的状态（并在初始计算期间进行转换时正确更新它).
有时，我们可以计算 PARENT(i, j) 而无需显式存储它。情况是这样的：
- 可以找出我们可以从哪些状态转换到当前状态。
- 我们可以检查一个转换是否为我们提供了该状态的最优解。

当我们知道每个状态的父级时，我们可以从最终状态开始迭代，将每个状态添加到一个列表中，然后继续到它的父级，直到我们到达起始状态（最后反转列表如有必要）。我们也可以递归地做同样的事情。

这是一个（可能微不足道的）例子：

假设我们正在解决一个标准问题：给定一个上面有数字的网格，如果我们只允许向右移动，则找到从左上角到右下角的路径的总和最大，或者下来。

显式计算父级（我在这里省略了极端情况）：

if dp(i - 1, j) > dp(i, j - 1) then
    dp(i, j) = a(i, j) + dp(i - 1, j)
    par(i, j) = (i - 1, j)
else
    dp(i, j) = a(i, j) + dp(i, j - 1)
    par(i, j) = (i, j - 1)

隐含地：

let getPar(i, j)
    if dp(i - 1, j) > dp(i, j - 1)
        return (i - 1, j)
    return (i, j - 1)

这个想法对于更复杂的问题是一样的。

打印动态规划解决方案中遍历的路径

Printing the path traversed in a dynamic programming solution

algorithm

state

graph

path

dynamic-programming