题目描述

图片描述已移除

方法一：动态规划

思路

改题存在如下递推关系：

f(n) = f(n-1) + f(n-2) + f(n-3)

即上 n 个台阶的总方式数等于跳一个台阶到最后一个台阶的方式数，加上跳两个台阶到最后一个台阶的方式数，再加上跳三个台阶到最后一个台阶的方式数。

相当于“三阶斐波那契数”。

初始化： f1= 1，f2=2，f3=4

迭代实现的代码如下，由于结果可能很大，所以f1,f2,f2,fn的类型定义为long，并且在每次计算fn时做了取余操作。该题递归实现会超时。

代码

class Solution {    public:    int waysToStep(int n) {            long f1 = 1, f2 = 2, f3 = 4, fn;        if (n <= 2) {                return n;        }        else if (n == 3) {                return 4;        }        for (int i = 3; i < n; ++i) {                fn = (f1 + f2 + f3) % 1000000007;            f1 = f2;            f2 = f3;            f3 = fn;        }        return fn;    }};