当前位置：首页 > article >正文

力扣面试题 39 - 三步问题 C语言解法

article 2024/12/27 7:33:19

题目：

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1:

 输入：n = 3 
 输出：4
 说明: 有四种走法

示例2:

 输入：n = 5
 输出：13

提示:

n范围在[1, 1000000]之间

思路：

找规律。写出n=1~5的情况，可以发现规律。
f(n) = f(n - 1) + f(n - 2) + f(n - 3)
如果使用递归，可以完成题目，但时间效率过低，呈指数级，因此需要优化
采用动态规划的思想优化算法，关于动态规划可以看我的这一篇什么是动态规划？内含代码示例-CSDN博客

先上错误答案，该代码无法通过测试用例，会超过系统响应时间！

原因分析：

default 分支使用递归计算 waysToStep(n - 1) + waysToStep(n - 2) + waysToStep(n - 3)，但没有优化。
直接递归会导致重复计算，时间复杂度是指数级，效率非常低。

int waysToStep(int n) {
    int ret = 0;
    switch(n){
        case 1: ret = 1;break;
        case 2: ret = 2;break;
        case 3: ret = 4;break;
        default: 
        ret = waysToStep(n - 1) + waysToStep(n - 2) + waysToStep(n - 3);break;
    }
    return ret % 1000000007;
}

下面是正确答案：

int waysToStep(int n) {
    if(n == 1) return 1;
    if(n == 2) return 2;
    if(n == 3) return 4;
    int dp[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for(int i = 4; i <= n; i++){
        dp[i] = ((dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3]) % 1000000007;
    }
    return dp[n];
}

我猜可能有小伙伴会疑惑，为什么要取模1000000007这个数字呢？

1. 防止结果溢出

在计算过程中，随着 nnn 的增大，结果 f(n)的数值可能非常庞大，远超出普通整型数据类型（如 int 或 long）的存储范围。