解题思路：动态规划

先观察 1级台阶 1种方法

            2级台阶 2种方法

            3级台阶 4种方法

            4级台阶 7种方法 

            5级台阶 13种方法 

可以看出规律 从3级台阶后 每级台阶需要从前三层台阶和相加

注意：后面值会过大  需要在相加之后就模运算1000000007

代码如下

class Solution {
public:int waysToStep(int n) {vector<int> dp (n+1);if(n==1||n==2) return n;if(n==3) return  4;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];}
};