矩形网格中的角到角最短路径
本文关键字：最短路径 网格 | 更新日期: 2023-09-27 18:24:03
我在一次面试中遇到了这个问题，但我无法解决。用于计算mxn网格从botton左到右上角的最短路径数的代码。如何解决这个问题？
假设你想解决它，但不是解决方案：考虑1x1，1x2，（m-1）x（n-1）
https://en.wikipedia.org/wiki/Dynamic_programming
https://en.wikipedia.org/wiki/Memoization
这个问题是这个问题的一个私人案例，你只限于以右上角结束的所有传球。
对于单纯形，我们假设n * n矩阵[稍后可以推广到m * n。
请注意，从一个角落到另一个角落的每条路径都有个2n移动，其中n移动是"向上"的，其余移动是"向右"的
因此，您可以用长度为2n的所有二进制向量来表示您的路径，其中n位恰好设置为1。
这样的二进制矢量的数量可以用O(1):choose(2n,n)中的闭合公式来计算。
将其推广到n * m矩阵：想想，从一个角落到另一个角落的路径有多少步？他们中有多少人是"对的"？对新矩阵隐含选择公式，并确保它给你的结果与我们之前对n=m 得到的结果相同