路径只能从 (0,0) 开始在网格中向左和底部移动。最终需要到达 (N-1, N-1)。
如果网格是NxN，则有2N条选择N条这样的路径，随着N的增加呈指数增长，由于内存限制，我无法将所有这些路径存储在列表中。我们还可以将每条路径编码为长度为 2^(N-1) 的比特串，其中 1 是向右移动，0 是向下移动。每个编码路径中的 0 和 1 数量相等。
我得到了一个尺寸为 NxN 的二维方形网格。网格中的每个单元格都有一个非负值。我需要对每个唯一路径的所有这些值进行求和。我怎样才能有效地做到这一点？
最佳答案
我们将值矩阵称为 V，因此 V[y][x] 是单元格 (x, y) 处的值。
每条路径都从 (0, 0) 开始，到 (N - 1, N - 1) 结束。路径 P 的总值，value(P) 是位于 P 上的所有单元格的值之和。
问题是计算从 (0, 0) 到 (N - 1, N -1) 的所有有效路径 P 的 SUM(value(P))。
计算 SUM 的另一种方法是计算每个单元格 (x, y) 有多少条路径经过该单元格，而不是枚举每个有效路径。如果有 i 条路径经过该单元格，则该单元格贡献的总值(value)为 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 种方法从 (0, 0) 经 (x, y) 到达 (N-1, N-1)。休息很容易。
关于java - 2D 网格中从 (0,0) 到 (N-1, N-1) 的独特路径，具有扭曲，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27262125/