题目链接

数楼梯

题目描述

给定一段有 阶的楼梯，你每一步可以选择上 1 阶或者 2 阶。求从楼梯底端走到顶端共有多少种不同的走法。由于答案可能很大，请将结果对 取模后输出。

输入:

  • 一个整数 ，表示楼梯的阶数。

输出:

  • 一个整数，表示不同走法的数量，对 取模后的结果。

解题思路

这是一个非常经典的动态规划问题，其本质是求解斐波那契数列。

  1. 定义状态: 我们用 表示走到第 阶楼梯的不同走法数量。我们的目标是求出 。

  2. 状态转移方程: 要想到达第 阶楼梯，只有两种可能的前一步：

    • 从第 阶楼梯再上 1 阶。
    • 从第 阶楼梯再上 2 阶。 因此，到达第 阶的总走法数量，是到达第 阶和第 阶的走法数量之和。这给我们带来了状态转移方程：

  3. 确定边界条件 (Base Cases):

    • 对于第 1 阶楼梯 ()，只有一种走法：上 1 阶。所以 。
    • 对于第 2 阶楼梯 ()，有两种走法：上两次 1 阶 (1+1)，或者上一次 2 阶 (2)。所以 。

  4. 空间优化: 观察状态转移方程可以发现，计算 只需要 和 这两个前序状态。因此，我们不需要一个大小为 的数组来存储所有中间状态，只需要用两个变量滚动记录前两个状态即可，这可以将空间复杂度从 优化到 。 我们可以用变量 和 分别表示 和 。在每次迭代中，计算出当前的 ，然后更新 和 为下一个迭代做准备。

  5. 取模运算: 由于题目要求结果对 取模，我们需要在每次加法运算后都进行取模操作，以防止中间结果溢出。

代码

#include <iostream>

using namespace std;

const int MOD = 998244353;

int main() {
    int n;
    cin >> n;

    if (n <= 2) {
        cout << n << endl;
        return 0;
    }

    long long a = 1; // dp[1]
    long long b = 2; // dp[2]
    long long current;
    
    for (int i = 3; i <= n; ++i) {
        current = (a + b) % MOD;
        a = b;
        b = current;
    }

    cout << b << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    private static final int MOD = 998244353;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        if (n <= 2) {
            System.out.println(n);
            return;
        }

        long a = 1; // dp[1]
        long b = 2; // dp[2]
        long current;
        
        for (int i = 3; i <= n; i++) {
            current = (a + b) % MOD;
            a = b;
            b = current;
        }
        
        System.out.println(b);
    }
}

n = int(input())
MOD = 998244353

if n <= 2:
    print(n)
else:
    a = 1  # dp[1]
    b = 2  # dp[2]
    
    for _ in range(3, n + 1):
        current = (a + b) % MOD
        a = b
        b = current
        
    print(b)

算法及复杂度

  • 算法：动态规划（滚动数组优化）
  • 时间复杂度： - 我们需要进行一次从 3 到 的循环。
  • 空间复杂度： - 只使用了常数个变量来存储状态。