使用 C++ 查找网格中从一点到另一点的路径数

在本文中，我们得到一个问题，我们需要找到从点 A 到点 B 的总路径数，其中 A 和 B 是固定点，例如，A 是网格中的左上角点，B 是网格中的右下角点。

Input : N = 5
Output : 252

Input : N = 4
Output : 70

Input : N = 3
Output : 20

在给定的问题中，我们可以通过简单的观察来形式化答案并得到结果。

寻找解决方案的方法

在这种方法中，我们根据观察结果为给定问题制定了一个公式，即为了遍历网格从 A 到 B，我们需要向右移动 n 次，向下移动 n 次，这意味着我们需要找到所有这些路径组合的可能性，从而得到 (n+n) 和 n 的组合公式。

示例

#include<bits/stdc++.h>

using namespace std;
int fact(int n){ // factorial function 
   if(n <= 1)
      return 1;
   return n * fact(n-1);
}
int main() {
   int n = 5; // given n
   int answer = 0; // our answer
   answer = fact(n+n); // finding factorial of 2*n
   answer = answer / (fact(n) * fact(n)); // (2*n)! / (n! + n!)
   cout << answer << "\n";
}

输出

252

以上代码的解释

在此代码中，我们计算了 2*n 到 n 的组合公式，因为我们知道要从点 A 移动到点 B，我们将需要精确的 2*n 个操作，两个方向各 n 个操作，因此我们找到所有这些操作的可能组合，即 (2*n)!/ (n! + n!)。给定程序的总体时间复杂度为 O(1)，这意味着我们的复杂度不依赖于给定的 n。

结论

在本文中，我们讨论了一个问题，即查找网格中从一点到另一点的路径数。我们还学习了此问题的 C++ 程序以及我们解决的完整方法。我们可以在其他语言（如 C、Java、Python 等）中编写相同的程序。我们希望本文对您有所帮助。

更新于： 2021年11月26日

194 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告