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

个人主页: 起名字真南的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 ) 级台阶的方法数：

1. 初始值：

   • ( ways(1) = 1 )
   • ( ways(2) = 2 )
   • ( ways(3) = 4 )

2. 状态转移方程：

   • ( 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 为 b
            b = c; // 更新 b 为 c
            c = ret; // 更新 c 为当前结果
        }

        return c; // 返回最终结果
    }
};

---

代码要点

• 取模运算：为避免整数溢出，在计算 a + b 和加上 c 时分别取模 ( \mod 10^9+7 )。
• 初始值设置：根据题意直接设置 ( ways(1) = 1 )，( ways(2) = 2 )，( ways(3) = 4 )。
• 迭代更新：通过三个变量 a、b 和 c 滚动更新，无需额外空间。

---

总结

• 递归与动态规划：递归形式简单但效率低，动态规划通过状态转移优化性能。
• 时间复杂度优化：从递归的指数时间复杂度 ( O(3^n) ) 降至线性时间 ( O(n) )。
• 空间复杂度优化：仅用三个变量存储中间状态，节省内存。

---

如果有疑问或改进建议，欢迎在评论区留言！ 😊

原文地址：https://blog.csdn.net/weixin_74837455/article/details/144436302

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！