题解 | #数楼梯#

数楼梯

https://www.nowcoder.com/practice/c7e5f164fa5d471f8f83c90fe4ee3f05

题目链接

数楼梯

题目描述

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

解题思路

这是一个经典的动态规划问题。

我们定义 $dp[i]$ 为到达第 $i$ 阶楼梯的不同走法数量。要想到达第 $i$ 阶楼梯，最后一步只可能是从第 $i-1$ 阶或第 $i-2$ 阶上来的：

从第 $i-1$ 阶走 $1$ 阶上来，这种情况的走法数量等于到达第 $i-1$ 阶的走法数量，即 $dp[i-1]$ 。
从第 $i-2$ 阶走 $2$ 阶上来，这种情况的走法数量等于到达第 $i-2$ 阶的走法数量，即 $dp[i-2]$ 。

因此，可以得到状态转移方程： $dp[i] = dp[i-1] + dp[i-2]$

接下来确定初始状态（边界条件）：

对于第 $1$ 阶楼梯，只有一种走法（走 $1$ 阶），所以 $dp[1] = 1$ 。
对于第 $2$ 阶楼梯，有两种走法（“1阶+1阶” 或 “2阶”），所以 $dp[2] = 2$ 。

我们可以从 $i=3$ 开始，根据状态转移方程依次计算出 $dp[n]$ 的值。

在实现时，我们注意到计算 $dp[i]$ 只需要 $dp[i-1]$ 和 $dp[i-2]$ 的值。因此，没有必要用一个数组来存储所有的 $dp$ 值，只需用两个变量滚动地记录前两项即可。这样可以将空间复杂度从 $\mathcal{O}(n)$ 优化到 $\mathcal{O}(1)$ 。

代码

c++
java
python

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << 1 << "\n";
        return 0;
    }
    if (n == 2) {
        cout << 2 << "\n";
        return 0;
    }
    // a 表示 dp[i-2]，b 表示 dp[i-1]
    long long a = 1, b = 2;
    long long mod = 998244353;
    for (int i = 3; i <= n; i++) {
        long long c = (a + b) % mod;
        a = b;
        b = c;
    }
    cout << b << "\n";
    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();
        if (n == 1) {
            System.out.println(1);
            return;
        }
        if (n == 2) {
            System.out.println(2);
            return;
        }
        // a 表示 dp[i-2]，b 表示 dp[i-1]
        long a = 1, b = 2;
        long mod = 998244353;
        for (int i = 3; i <= n; i++) {
            long c = (a + b) % mod;
            a = b;
            b = c;
        }
        System.out.println(b);
    }
}

n = int(input())

if n <= 2:
    print(n)
else:
    # a, b 分别表示 dp[i-2] 和 dp[i-1]
    a, b = 1, 2
    mod = 998244353
    # 从第 3 阶开始计算
    for i in range(3, n + 1):
        # 滚动更新
        a, b = b, (a + b) % mod
    print(b)