[蓝桥杯]求解台阶问题

求解台阶问题

题目描述

现一个算法求解台阶问题。介绍如下：

• 对于高度为 nn 的台阶，从下往上走，每一步的阶数为 1，2，3 中的一个。问要走到顶部一共有多少种走法。

输入描述

输入一个数字 N (1≤N≤35)N (1≤N≤35)，表示台阶的高度。

输出描述

输出一行，为走法总数。

输入输出样例

示例

输入

4

输出

 7

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

• 台阶问题解法（动态规划）

• 对于高度为 n 的台阶，每次可走 1、2 或 3 步，求走法总数的问题，可通过动态规划高效解决。其核心递推公式为：
  f(n)=f(n−1)+f(n−2)+f(n−3)(n≥3)
  基础情况为：

• f(0)=1（无台阶时视为 1 种方式）
• f(1)=1（仅 1 种方式：走 1 步）
• f(2)=2（2 种方式：1+1 或 2）
• ​​初始化基础值​​
  直接处理 n=0,1,2 的情况。
• ​​动态规划递推​​
  使用滚动变量优化空间复杂度（O(1)）：
  • 定义 a = f(0), b = f(1), c = f(2)
  • 从 i=3 开始迭代至 n：
    • 计算当前值 current = a + b + c
    • 滚动更新：a = b, b = c, c = current
• ​​输出结果​​
  最终 c 即为 f(n)。

  #include <iostream>
  using namespace std;int main() {int n;cin >> n;// 处理基础情况if (n == 0 || n == 1) {cout << 1 << endl;return 0;}if (n == 2) {cout << 2 << endl;return 0;}// 动态规划（滚动变量优化）long long a = 1, b = 1, c = 2;  // 使用 long long 防止溢出for (int i = 3; i <= n; i++) {long long current = a + b + c;a = b;b = c;c = current;}cout << c << endl;return 0;
  }

  复杂度分析

• ​​时间复杂度​​：O(n)，仅需单次遍历。
• ​​空间复杂度​​：O(1)，仅用 3 个变量存储状态。

示例验证

输入 n	输出 f(n)	走法分解（共 f(n) 种）
1	1	1
2	2	1+1, 2
3	4	1+1+1, 1+2, 2+1, 3
4	7	1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1