Solutions of Hakurei Shrine

Select solution language

phphongyd Created at 26 likes

Hiểu bài toán: Vấn đề: Tìm số cách để leo n bậc thang khi mỗi bước có thể là 1, 2 hoặc 3 bậc. Phương pháp: Sử dụng quy hoạch động (dynamic programming) để giải quyết bài toán đệ quy này. Ý tưởng: Gọi dp[i] là số cách lên i bậc thang. Để lên bậc i, ta có thể: Bước 1 bậc từ bậc i-1: dp[i] += dp[i-1] Bước 2 bậc từ bậc i-2: dp[i] += dp[i-2] Bước 3 bậc từ bậc i-3: dp[i] += dp[i-3] Code C++: ``` #include <bits/stdc++.h> using namespace std; const int MOD = 1e9+7; // Số dư khi chia cho 10^9 + 7 int main() { int n; cin >> n; long long dp[n + 1]; dp[0] = 1; // Có 1 cách để lên 0 bậc thang dp[1] = 1; // Có 1 cách để lên 1 bậc thang dp[2] = 2; // Có 2 cách để lên 2 bậc thang (1+1 hoặc 2) // Duyệt từ bậc 3 đến bậc n for (int i = 3; i <= n; ++i) { dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD; } cout << dp[n] << endl; return 0; } ```