Lời giải: Magic Staircase (Cầu Thang Thần Kỳ)

Phân tích bài toán

Tại mỗi bậc \(i\), ta có thể bước đến từ bậc \(i-1\) (bước 1 bậc) hoặc từ bậc \(i-2\) (bước 2 bậc). Gọi \(dp[i]\) là số cách bước lên bậc \(i\). Công thức quy hoạch động: \[dp[i] = dp[i-1] + dp[i-2]\] Với cơ sở \(dp[1] = 1, dp[2] = 2\). Lưu ý: Nếu số cách lớn, cần lấy modulo theo yêu cầu của bài toán hoặc lưu bằng số nguyên 64-bit (long long).

Độ phức tạp thuật toán

• Thời gian: \(O(N)\).
• Không gian bộ nhớ: \(O(1)\) chỉ cần lưu 2 giá trị liền trước.

Mã nguồn C++ tham khảo

#include <iostream>
#include <vector>

using namespace std;

const long long MOD = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    if (n == 1) {
        cout << 1 << "\n";
        return 0;
    }

    long long prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; ++i) {
        long long curr = (prev1 + prev2) % MOD;
        prev2 = prev1;
        prev1 = curr;
    }

    cout << prev1 << "\n";
    return 0;
}