Hướng giải của Đếm đường đi

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Ý tưởng: Đệ quy: count(i, j) = count(i+1, j) + count(i, j+1) với base case \((n,m)=1\). Hoặc dùng DP \(O(n \cdot m)\) với dp[i][j] = dp[i-1][j] + dp[i][j-1].

Độ phức tạp: \(O(2^{n+m})\) với đệ quy thuần, \(O(n \cdot m)\) với DP.

C++

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

int n, m;
long long dp[12][12];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (i == 1 || j == 1) dp[i][j] = 1;
            else dp[i][j] = dp[i-1][j] + dp[i][j-1];
    cout << dp[n][m] << "\n";
    return 0;
}

Python

# Dùng tổ hợp (công thức): C(n+m-2, n-1)
from math import comb
n, m = map(int, input().split())
print(comb(n + m - 2, n - 1))

Nhận xét

Không có ý kiến tại thời điểm này.