本文共 659 字，大约阅读时间需要 2 分钟。

题目描述

图片描述已移除

方法一：动态规划

思路

改题存在如下递推关系：

初始化： 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;    }};