我想使用动态编程技术编写一个算法，该算法执行以下操作：查找沿具有 n × n 方形单元格的网格边缘的单调路径数，这些单元格不超过对角线。单调路径是从左下角开始，在右上角结束，并且完全由指向右侧或向上的边组成的路径。
我有一些想法，但无法弄清楚如何正确地做到这一点。
问问题
918 次
3 回答
2
0 x 0首先，通过解决退化案例（网格）找到递归的基础。然后通过想象问题的那一部分（例如，已经解决）来寻找重复步骤，K x M看看您是否可以通过添加一行或一列来扩展该解决方案，使解决方案K+1 x M或K x M+1. 这应该很简单：对于您添加的每个点，查看网格点是否在对角线下方，然后将从底部和左侧通向该点的路径数相加。其中一个点位于 中K x M，另一个位于您正在构建的附加行或列中。
有了退化的情况和递归步骤，首先解决一个0 x N问题，然后1 x N，然后2 x N等等，直到你有你的解决方案，来构建你的解决N x N方案。
于 2012-01-21T17:28:15.837 回答
1
这是一个只考虑方形网格的可能递归。
在n×n网格上有两种不与对角线相交的单调路径：那些在某个中间点(i,i)接触对角线且0 < i < n的路径，以及不与对角线相交的路径。
在n×n网格上首先在(i,i)处接触对角线的路径可以分成两部分：一条在i×i网格上不接触对角线的路径，另一条在(ni)×(ni )网格和 thay 可能接触对角线。这表明您可以通过考虑所有可能 i 的递归来计算那些。
不接触对角线的路径将以“右”开始，以“上”结束。在这两个移动之间是一个在(n-1)×(n-1)网格上的单调路径，它不穿过对角线但可能会碰到它。
我们在这里计算的是第n个 加泰罗尼亚数。如果你想验证你的递归计算，它有一个公式。
于 2012-01-24T07:45:23.623 回答
0
设到达坐标的路径数(i,j)为P(i,j)。因此（假设左下角是(0,0)）：
P(i,j) = P(i-1,j) + P(i,j-1)
您可以进一步设置不低于对角线的坐标条件。即：i范围从0..n，j范围从0..n，但i<=j总是。
于 2012-01-26T21:19:36.840 回答