Đếm số đường đi từ góc trên trái đến góc dưới phải trong lưới N×N bằng C++

Cho lưới N×N, bắt đầu (0,0) đích (N,N). Chỉ đi phải hoặc xuống. Số đường đi = tổ hợp C(2N, N) = (2N)! / (N!)². Ví dụ:

N=5 → 252, N=4 → 70, N=3 → 20

Ví dụ

#include<bits/stdc++.h>
using namespace std;

long long fact(int n) { return n <= 1 ? 1 : n * fact(n-1); }

int main() {
    int n = 5;
    long long ans = fact(2*n) / (fact(n) * fact(n));
    cout << ans << "\n";
    return 0;
}

Kết quả

252

Kết luận

Số đường đi trong lưới N×N chỉ đi phải/xuống = tổ hợp C(2N, N). Tính bằng giai thừa O(N) hoặc tối ưu hơn. Code C++.