题目链接：leetcode三步问题
目录
题目解析：
算法原理:
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
编写代码:
题目解析：
题目让我们求小孩到达n阶台阶的时候，可以有多少上楼梯方式；
由题可得：
小孩一次可以上1阶、2阶或3阶：
我们这里逐个在每一阶的上楼方式分析一下，看看有什么规律：
1.假设n=1，即到达一阶：
显然，我们只有一种方式：只跳一阶即可直达。
2.当n=2，即到达2阶：
第一种方式：
我们可以从0开始一步直接到达2的位置（0-->2）
所以有一种方法：
第二种方式是：
不管你用什么方法，跳到1后，再从1加一步跳到2；
显然，我们跳到1台阶只有0-->1这一种方法，我们只需再跳一步0-->1-->2,就可从1到达2；
所以有一种方法：
所以到达台阶2一共有两种方法：
3.当n=3，即到达3阶：
第一种方式：
我们可以从0开始一步直接到达3的位置（0-->3），
所以有一种方法：
第二种方式是：
不管你用什么方法，跳到1后，再从1加一步直接跳到3；
显然，我们跳到1台阶只有0-->1这一种方法，我们只需再跳一步0-->1-->3,就可从1到达3；
所以有一种方法：
第二种方式是：
不管你用什么方法，跳到2后，再从2加一步直接跳到3；
显然，我们跳到2台阶有（0-->2）和(0-->1-->2)这两种方法，
我们只需再跳一步
0-->2-->3
0-->1-->2-->3
就可从2到达3；
所以有两种方法
所以到达台阶2一共有4种方法：
4.当n=4，即到达4阶：
第一种方式：
不管你用什么方法，跳到1后，再从1加一步直接跳到4；
显然，我们跳到1台阶只有0-->1这一种方法，我们只需再跳一步0-->1-->4,就可从1到达4；
所以有一种方法：
第二种方式是：
不管你用什么方法，跳到2后，再从2加一步直接跳到4；
显然，我们跳到2台阶有（0-->2）和(0-->1-->2)这两种方法，
我们只需再跳一步
0-->2-->4
0-->1-->2-->4
就可从2到达4；
所以有两种方法
第二种方式是：
不管你用什么方法，跳到3后，再从3加一步直接跳到4；
显然，我们跳到3台阶有这4种方法，
我们只需再跳一步，根据以上规律：
……-->3-->4
……-->3-->4
……-->3-->4
……-->3-->4
就可从3到达4；
所以有四种方法
所以到达台阶4一共有1（方式一：直接从1->4）+2（方式二：直接从2->4）+4（方式三：直接从3->4）种方法（7种）：
分析到这里：我们可以得到一个规律：
到达某一阶的方法=到达它前三阶的方法的和
算法原理:
1.状态表示
先创建一个dp表
首先先思考dp表里面的值所表示的含义（是什么？）
dp[i]表示到达i台阶一共有多少种方法。
这种状态表示怎么来的？
1.题目要求
小孩到达某台阶一共有多少方法
2.经验+题目要求
经验：以i位置为结尾，分析它前面几步的状态；
2.状态转移方程
dp[i]等于什么？
综上分析：
dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
3.初始化
(保证填表的时候不越界)
由题目得：n范围在[1, 1000000]之间
从上面的dp[i]公式，我们发现当i=1、2、3时等号后面的dp[i-1]、dp[i-2]、dp[i-3]会越界
所以我们这里需要将i=1、2、3初始化，并在写代码时在前面先条件判断；
4.填表顺序
（为了填写当前状态的时候，所需要的状态已经计算过了）
这里所需要的状态是：
这里所需要的状态是：dp[i-1]、dp[i-2]、dp[i-3]；
这几个数都是在i之前的，
所以我们这里是从左向右填表；
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;
else if(n==2)
return 2;
else if(n==3)
return 4;
else
{
vector<int> dp(n+1);
dp[1]=1;dp[2]=2;dp[3]=4;
for(int i=4;i<n+1;i++)
{
dp[i]=((dp[i-1]+dp[i-2])% MOD+dp[i-3])% MOD;
}
return dp[n];
}
}
};
