Leetcode 面试题 08.01. 三步问题【C++】

本文最后更新于:2020年8月29日 下午

地址:https://leetcode-cn.com/problems/three-steps-problem-lcci/

题目

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

示例1:

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

示例2:

输入:n = 5
输出:13

提示:

  1. n范围在[1, 1000000]之间

解题思路

动态规划问题,满足【最优子结构】和【无后效性】,找【状态】,找【转移方程】。

  • 状态:i个台阶有多少种上楼梯方式;

  • 转移方程:F[i] = (F[i - 1] + F[i - 2] + F[i - 3]) % 1000000007。

只考虑最后一步,要上到第i阶楼梯可能的方法有最后一步分别上了1阶、2阶、3阶,对应3种,而对应第i阶可能的方法F[i]则为前三种情况的方法数的总和。

需要注意由于方法数太多可能越界,因此虽然转移方程逻辑上是没问题的,但在代码中最好逐项相加后立即求余,然后再继续加。

源码

class Solution {
public:
    int waysToStep(int n) {
        int mod = 1000000007;
        int f1 = 1;  //1、2、3阶楼梯的方法很容易得出
        int f2 = 2;
        int f3 = 4;
        if(n == 1) return f1;
        else if(n == 2) return f2;
        else if(n == 3) return f3;
        int fi;  //大于3阶的楼梯数
        for(int i = 4; i <= n; i++){
            fi = ((f1 + f2) % mod  + f3) % mod;  // 需要先求余后再相加,否则可能溢出
            f1 = f2;
            f2 = f3;
            f3 = fi;
        }
        return fi;
    }
};