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

地址：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;
    }
};