矩形网格中的角到角最短路径

假设你想解决它，但不是解决方案：考虑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 得到的结果相同