java - 具有扭曲的二维网格中从 (0,0) 到 (N-1, N-1) 的唯一路径

Question

路径只能在从 (0,0) 开始的网格中向左和底部移动。最终它需要到达 (N-1, N-1)。

如果网格是 NxN，则有 2N 条选择 N 条这样的路径，随着 N 的增加呈指数增长，由于内存限制，我无法将所有这些路径存储在列表中。我们还可以将每条路径编码成长度为 2^(N-1) 的位串，其中 1 为右移，0 为下移。每个编码路径中有相等数量的 0 和 1。

我得到了一个 NxN 维的二维正方形网格。网格中的每个单元格都有一个非负值。我需要对每个唯一路径的所有这些值求和。我怎样才能有效地做到这一点？

Answer 1

我们称值矩阵为 V，因此 V[y][x] 是单元格 (x, y) 的值。

每条路径都从 (0, 0) 开始，到 (N - 1, N - 1) 结束。一条路径P的总值，value(P)是P上所有cell的值之和。

问题是计算从 (0, 0) 到 (N - 1, N -1) 的所有有效路径 P 的 SUM(value(P))。

计算 SUM 的另一种方法不是枚举每条有效路径，而是计算每个单元格 (x, y) 有多少条路径穿过该单元格。如果有 i 条路径经过这个单元格，那么这个单元格贡献的总值就是 i * V[y][x]。因此，我们只需遍历网格中的每个单元格，为其计算 i(x, y)，将 i(x, y) * V[y][x] 添加到总结果中。

如何计算 i(x, y)？ i(x, y) 就是编号。从 (0, 0) 通过 (x, y) 到 (N-1, N-1) 的有效路径的数量。提示:- 如果有一种方法可以从 (0, 0) 到达 (x, y) 并且有 b 种方法可以从 (x, y) 到达 (N-1, N-1)，那么就有 a * b 种方法可以通过 (x, y) 从 (0, 0) 到达 (N-1, N-1)。休息很容易。