时间戳

首页 > 解决方案 > 通过 DP 打印 mXn 矩阵从左上角到右下角的所有可能路径

c++ - 通过 DP 打印 mXn 矩阵从左上角到右下角的所有可能路径

问题描述

我无法通过使用动态编程“打印从 mXn 矩阵的左上角到右下角的所有可能路径” 。在大多数站点中，我看到它是通过递归完成的，具有指数时间复杂度。任何人都可以为我提供任何参考或任何链接来为这个问题创建一个 c++ 程序......您可以在任何步骤中仅向右或向下移动矩阵。正如我所说，我无法理解这意味着我没有开始任何事情......谢谢。

标签： c++algorithmmatrixdynamic

解决方案

由于您有指数路径，因此如果您必须打印所有这些路径，则无法从指数时间开始运行。另一方面，如果你只是想计数，它可以做得更快。

打印所有路径的简单递归解决方案：

print_path(x, y, path){
    if(x == height && y == width) print(path)
    if(x < height) print_path(x + 1, y, path + (x, y))
    if(y < width)  print_path(x, y + 1, path + (x, y))

如果你只想数数，你可以使用 DP。假设您从 (0,0) 开始并在 (2,2) 结束。首先要注意，当在 (2,i) 或 (i,2) 中时，您只有一种方法可以到达 (2,2)，它是直行的：

0 0 1
0 0 1
1 1 1

现在，对于从 (1,1) 开始的每个 0 元素，从那里开始到终点的路径数是其右侧单元格与其底部单元格的总和：

0 0 1        0 0 1        0 3 1        6 3 1
0 2 1   =>   3 2 1   =>   3 2 1   =>   3 2 1
1 1 1        1 1 1        1 1 1        1 1 1

所以你的答案是 6。当你遍历矩阵的所有单元格时。复杂度为 O(n²)。虽然，您可以使用方阵总是对称的事实，并且 NxN 矩阵的最终值将是 N 的中心二项式系数。这可以大大降低复杂性。例如，如果你的矩阵是 5x7，你可以推导出矩阵的所有对角线：

0  0 70  0  0  0  0
0  0  0 20  0  0  0
0  0  0  0  6  0  0
0  0  0  0  0  2  0
0  0  0  0  0  0  1

推荐阅读