用动态规划编写递归算法
我想使用动态编程技术编写一个算法，该算法执行以下操作： 求沿具有 n × n 方格的网格边缘的单调路径的数量，这些路径不通过对角线上方。单调路径是一种从左下角开始、在右上角结束、并且完全由指向右侧或向上的边组成的路径。
我有一些想法，但不知道如何正确实施。
I want to write an algorithm using a dynamic programming technique, which does the following:
Find number of monotonic paths along the edges of a grid with n × n square cells, which do not pass above the diagonal. A monotonic path is one which starts in the lower left corner, finishes in the upper right corner, and consists entirely of edges pointing rightwards or upwards.
I had some ideas, but can't figure out how to do it right.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
首先，通过解决退化情况（
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< /code> 依此类推，直到获得N x N解决方案。First, find a base for your recursion by solving a degenerate case (a
0 x 0grid). Then look for a recurrence step by imagining that part of the problem, say,K x Mis already solved, and see if you can expand upon that solution by adding one row or one column to it, making the solutionK+1 x MorK x M+1. This should be simple: for each point you add, see if a grid point is below the diagonal, and then add up the number of paths leading to that point from the bottom and from the left. One of these points would be in theK x M, the other would be in the additional row or column that you are building.With the degenerate case and a recursive step in hand, build your solution by first solving a
0 x Nproblem, then1 x N, then2 x Nand so on, until you have yourN x Nsolution.这是仅考虑方形网格的可能递归。
n×n 网格上有两种不穿过对角线的单调路径：那些在某个中间点 (i,i) 与 (i,i) 接触对角线的路径em>0 <我< n，以及那些没有的。
首先在 (i,i) 处接触对角线的 n×n 网格上的路径可以分为两部分：i 上的一条路径×i 网格不接触对角线，另一个网格位于 (ni)×(ni) 网格上并且可能接触对角线。这表明您可以使用考虑所有可能 i 的递归来计算那些。
不接触对角线的路径将以“右”开始，以“上”结束。在这两个移动之间是 (n-1)×(n-1) 网格上的单调路径，该路径不穿过对角线，但可能接触它。
我们在这里计算的是第nth加泰罗尼亚数字。如果你想验证你的递归计算，有一个公式。
Here is a possible recursion that considers only square grids.
There are two kinds of monotone paths over the n×n grid that do not cross the diagonal: those that touch the diagonal at some intermediate point (i,i) with 0 < i < n, and those that don't.
A path over the n×n grid that first touches the diagonal at (i,i) can be split in two: one path over the i×i grid that does not touch the diagonal, and another over the (n-i)×(n-i) grid and thay may touch the diagonal. This suggests that you can count those with a recursion that considers all possible i.
A path that does not touch the diagonal will start with "right", and end with "up". Between these two moves is a monotone path over a (n-1)×(n-1) grid that does not cross the diagonal but may touch it.
What we are computing here is the nth Catalan number. There is a formula for it if you want to verify your recursive computation.
设到达坐标
(i,j)的路径数为P(i,j)。因此（假设左下角是(0,0)）：您可以进一步设置坐标不低于对角线的条件。即：
i的范围是0..n，j的范围是0..n，但是i<=j总是。Let number of path reaching coordinate
(i,j)beP(i,j). Therefore (assuming bottom left corner is(0,0)):You can further put conditions of coordinate not going below the diagonal. That is:
iranges from0..n,jranges from0..n, buti<=jalways.