【OJ题解】面试题三步问题

ops/2024/12/18 3:17:24/

个人主页: 起名字真南的CSDN博客

个人专栏:

【数据结构初阶】 📘 基础数据结构
【C语言】 💻 C语言编程技巧
【C++】 🚀 进阶C++
【OJ题解】 📝 题解精讲

题目链接

三步问题

解题思路

1. 问题分析

小明在上楼时可以选择每次上 1 个台阶、2 个台阶 或 3 个台阶，需要计算总共有多少种方法能爬上 ( n ) 级台阶。

2. 递归思路

将问题分解为子问题：

每次可以上 1、2 或 3 个台阶，那么上到第 ( n ) 级台阶的方法数可以分为以下三种情况：
1. 从 ( n-1 ) 级跳上来（方法数为 ways(n-1)）。
2. 从 ( n-2 ) 级跳上来（方法数为 ways(n-2)）。
3. 从 ( n-3 ) 级跳上来（方法数为 ways(n-3)）。

于是有递推公式：
[
ways(n) = ways(n-1) + ways(n-2) + ways(n-3)
]

3. 优化方案：动态规划

使用动态规划减少重复计算，定义三个变量 a、b 和 c 分别记录上到 ( n-3 )、( n-2 )、( n-1 ) 级台阶的方法数：

初始值：
- ( ways(1) = 1 )
- ( ways(2) = 2 )
- ( ways(3) = 4 )
状态转移方程：
- ( ways(n) = (a + b + c) \mod 10^9+7 )
- 循环计算新的方法数，并依次更新 a、b、c 的值。

4. 时间与空间复杂度

时间复杂度： ( O(n) )，单次遍历计算。
空间复杂度： ( O(1) )，仅使用常数空间存储中间值。

代码实现

以下是 C++ 示例代码：

class Solution {
public:int waysToStep(int n) {const int MOD = 1000000007;  // 定义取模数if (n < 3) return n;        // 特殊情况：小于 3 的台阶直接返回if (n == 3) return 4;       // 特殊情况：3 级台阶直接返回int a = 1; // 1 级台阶的方法数int b = 2; // 2 级台阶的方法数int c = 4; // 3 级台阶的方法数int ret = 0;for (int i = 4; i <= n; i++) {ret = ((a + b) % MOD + c) % MOD; // 递推公式取模a = b; // 更新 a 为 bb = c; // 更新 b 为 cc = ret; // 更新 c 为当前结果}return c; // 返回最终结果}
};