使用更多方向的最大路径和问题的变体

Question

我不知道如何处理这个问题。

我们得到了一个 N*N 网格，其中列出了从位置 a 到位置 b 的成本。

网格中的每一行告诉我们从一个位置到另一个位置的成本（每个位置对应于成本数组中的一行）。（如果成本数组中行 a 出现在行 b 之后，我们说位置 a 大于位置 b。每行的索引是一个位置）。我们可以选择从任何给定位置开始，并且只访问每个位置一次。在我们访问的每个位置 p，我们必须已经访问了所有小于 p 的位置，或者没有小于 p 的位置。

costs[a][b] 给出了从位置 a 移动到位置 b 的成本。
costs[a][b] 不一定与 costs[b][a] 相同。
每个索引 a 的成本[a][a] = 0（成本数组中的对角线始终为 0）。

我们的任务是找到有效路径的最大成本总和。

如果成本数组是：

[[0, 9, 1],
 [5, 0, 2],
 [4, 6, 0]]

因此最大成本将为 13，因为最昂贵的有效路径从位置 2 -> 位置 0 -> 位置 1 开始。

第一行告诉我们从位置 0 到位置 0（保持在同一个位置，花费我们 0）、0 到位置 1（花费我们 9）和 0 到位置 2（花费我们 1)。第二行和第三行遵循相同的模式。

Answer 1

关于您可以访问的位置的要求意味着，在您从某个位置 i 开始后，您将被迫反复移动到较低的位置，直到您到达位置 0。此时，您必须连续上升通过所有未访问的位置。动态规划解决方案并不明显，但通过相当复杂的实现，您可以使用标准技术获得 O(n^3) DP 算法。

事实证明还有一个 O(n^2) 解决方案，这是最优的。它还使用 O(n) 额外的 space，这可能也是最优的。解决方案来自对我们访问结构的思考：有一个向下的索引序列（可能有间隙）以 0 结束，然后是一个从 0 开始的向上序列，其中包含所有其他索引。虽然有 2^n 个可能的子序列，所以我们必须考虑更多以加快速度。

两个序列

假设我们有 i 个位置，0, 1, ... i-1，并且我们将它们分成两个有序的子序列（0 除外，它位于两个序列的开头）。我们将这两个序列称为 U 和 D，分别表示向上和向下。其中一个必须在 i-1 结束。不失一般性，假设 U 以 i-1 结尾，D 以 j >= 0.

结尾

添加位置后会发生什么i？我们要么将其添加到 U 的末尾，以便我们的序列在 i 和 j 处结束，要么将其添加到 D 的末尾 所以我们的序列结束于 i-1 和 i。如果我们将它添加到 U，U 的路径和（我们将其定义为所有相邻索引的 cost[u][v] 的总和u,v in U) 增加 cost[i-1][i]。如果我们将位置添加到 D 的末尾，D 的路径和将增加 cost[i][j]（因为它是向下序列，我们翻转了相对于 U) 的索引。

事实证明，我们只需要在子序列增长时跟踪它们的端点，以及具有这些端点的任何一对子序列的最大组合路径和。如果我们让 (i, j) 表示 U 以 i 结束并且 D 以 j 结束的状态，我们可以想想我们怎么会到这里的。

例如，在 (8,5)，我们之前的状态必须有一个包含 7 的子序列，所以我们之前的状态必须是 (7,5).因此max-value(8,5) = max-value(7,5) + cost[7][8]。当两个端点相差不止一个时，我们总是只有一个前导状态。

现在考虑状态(8,7)。我们不可能来自 (7,7)，因为唯一允许出现在两个序列中的数字是 0。所以我们可以来自 (0,7), (1,7), ... (6,7) 中的任何一个：我们可以选择使我们的路径总和最大化的那个。

def solve(costs: List[List[int]]) -> int:
    n = len(costs)
    # Deal with edge cases
    if n == 1:
        return 0
    if n == 2:
        return max(costs[0][1], costs[1][0])

    ups = [costs[0][1]]
    downs = [costs[1][0]]

    # After iteration i, ups[j] denotes the max-value of state (i, j)
    # and downs[j] denotes the max-value of state (j, i)
    for i in range(2, n):
        ups.append(max(downs[j] + costs[j][i] for j in range(i - 1)))
        downs.append(max(ups[j] + costs[i][j] for j in range(i - 1)))

        up_gain   = costs[i-1][i]
        down_gain = costs[i][i-1]

        for j in range(i - 1):
            ups[j]   += up_gain
            downs[j] += down_gain

    return max(max(ups), max(downs))

使用更多方向的最大路径和问题的变体

Variation of max path sum problem using more directions

python

algorithm

recursion

dynamic-programming