题目来源
本题来源为：
题目描述
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
题目解析
我们模拟一下小孩上楼梯的过程，会很容易发现规律
算法原理
1.状态表示
经验+题目要求
而经验就是：以i位置为结尾+…
（对一维的dp而言，基本上就是两种：以i位置为结尾+…或者以i位置为开始+…）
…表示根据题目要求进行补充完整。
对于本题而言：
dp[i] 表示:到达i位置时,一共有多少种方法
2.状态转移方程
在推导时基本上就是：
以i位置的状态，最近的一步，来划分问题
对于本题而言：到达i位置需要分三种情况
因此状态方程为：
dp[i]=dp[i-3]+dp[i-2]+dp[i-1];
3.初始化
根据状态转移方程：本题为防止越界需要处理下标为1,2,3位置的值：
dp[1]=1; dp[2]=2; dp[3]=4;
4.填表顺序
根据状态转移方程，我们计算dp[i]位置的值需要i-1与i-2与i-3位置的值，因此我们的填表顺序为：从左往右
5.返回值
根据题目要求直接返回dp[n]
代码实现
class Solution { public: int waysToStep(int n) { // 1.创建dp表 // 2.初始化 // 3.填表 // 4.返回值 const int MOD=1e9+7; //处理边界情况： if(n==1) return 1; if(n==2) return 2; if(n==3) return 4; //创建dp表 vector<int> dp(n+1); //初始化 dp[1]=1; dp[2]=2; dp[3]=4; //填表： for(int i=4;i<=n;i++) { dp[i]=((dp[i-3]+dp[i-2])%MOD+dp[i-1])%MOD; } return dp[n]; } };
