【动态规划】02斐波那契数列模型_三步问题（easy）

题目链接：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];
        }

       
    }
};