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

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>

P.S.:如果这个问题看起来太明显了，我们深表歉意。

Answer 1

1. 您可以在计算期间显式存储此信息。也就是说，除了DP(i, j)，你还可以保存PARENT(i, j)，它代表了我们从中获得结果的状态(i, j)(并在初始计算期间进行转换时正确更新它)。

2. 有时，我们可以计算 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)

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