数楼梯

思路

经典的爬楼梯问题：一共 n 阶楼梯，每次可以走 1 阶或 2 阶，问有多少种走法。

稍微手算一下就能发现规律：

  • 1 阶：1 种
  • 2 阶：2 种（1+1 或 2）
  • 3 阶：3 种
  • 4 阶：5 种

设 表示走到第 阶的方案数。到第 阶只有两种方式——从第 阶走 1 步上来，或者从第 阶走 2 步上来，所以：

$$

初始值 （站在地面，算一种方案），。这就是斐波那契数列。

因为只需要前两个状态，所以用两个变量滚动一下就行了，空间 。注意过程中要对 998244353 取模。

代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    const int MOD = 998244353;
    if (n <= 1) {
        cout << 1 << endl;
        return 0;
    }
    long long a = 1, b = 1; // f(0), f(1)
    for (int i = 2; i <= n; i++) {
        long long c = (a + b) % MOD;
        a = b;
        b = c;
    }
    cout << b << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        final int MOD = 998244353;
        if (n <= 1) {
            System.out.println(1);
            return;
        }
        long a = 1, b = 1; // f(0), f(1)
        for (int i = 2; i <= n; i++) {
            long c = (a + b) % MOD;
            a = b;
            b = c;
        }
        System.out.println(b);
    }
}

n = int(input())
MOD = 998244353
if n <= 1:
    print(1)
else:
    a, b = 1, 1
    for i in range(2, n + 1):
        a, b = b, (a + b) % MOD
    print(b)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', line => {
    const n = parseInt(line.trim());
    const MOD = 998244353n;
    if (n <= 1) {
        console.log(1);
    } else {
        let a = 1n, b = 1n;
        for (let i = 2; i <= n; i++) {
            const c = (a + b) % MOD;
            a = b;
            b = c;
        }
        console.log(b.toString());
    }
    rl.close();
});

复杂度

  • 时间复杂度：，一次遍历。
  • 空间复杂度：，只用了两个变量滚动。