我遇到了一个问题，它被要求找出在 2D 坐标平面中从点 1 到达点 2 的独特方式的数量。
注意：这可以假设而不失一般性x1 < x2和y1 < y2。
此外，运动被限制在以下方式中。一个人只能向右或向上移动。表示有效的移动是 from(xa, ya)到(xb, yb)ifxa < xb和ya < yb。
在数学上，这可以通过 找到( [(x2-x1)+(y2-y1)]! ) / [(x2-x1)!] * [(y2-y1)!]。我也想过代码。
我有一些方法，我用动态编程进行编码，我的方法需要O([max(x2,y2)]^2)时间Theta( x2 * y2 )，我可以用上三角矩阵或下三角矩阵来管理。
你能想到其他一些运行时间少于这个的方法吗？我正在考虑一个递归解决方案，其中最小运行时间是O(max(x2,y2)).
一个简单有效的解决方案是数学解决方案。
让x2-x1 = n和y2-y1 = m。
您需要准确n地向右走，然后m向上走，剩下的就是确定它们的顺序。
这可以建模为n+m具有恰好n元素设置为 1
的元素的二进制向量的数量。
因此，可能性的总数是chose(n,n+m) = (n+m)! / (n! * m!)，这正是你得到的。
鉴于数学答案已被证明并且计算速度更快 - 我认为没有理由使用具有这些限制的不同解决方案。
如果您渴望在这里使用递归，那么二项式系数的递归公式可能很适合这里。
编辑： 您可能正在寻找乘法公式来计算它。
要计算答案，您可以使用以下公式：
(n+m)!/(n!m!)=(n+1)*(n+2)/2*(n+3)/3*…*(n+m)/m
所以伪代码是：
let foo(n,m) =
ans=1;
for i = 1 to m do
ans = ans*(n+i)/i;
done;
ans
乘法和除法的顺序很重要，如果修改它，即使结果不是很大，也可能会溢出。
我终于设法写了这篇文章来详细描述这个问题并完成了答案。这是相同的链接。http://techieme.in/dynamic-programming-distinct-paths-between-two-points/
试试这个公式：
ans = (x2-x1) * (y2-y1) + 1;