【学会动态规划】三步问题（2）

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

根据题目，我们可以模拟一下走楼梯的过程，

比如说这里有四级台阶：

小孩走到一级台阶有一种走法，就是直接走上去：

小孩走到二级台阶有两种走法，一种是直接走上去，

一种是以一级台阶作为起点，一步走上去：

小孩走到三级台阶有四种走法：

从平地直接走上去，这是一种走法；

以一级台阶为起点，而走到一级台阶有一种方法，所以从一级台阶直接走上去是一种走法；

以二级台阶为起点，而到二级台阶有两种方法，所以以二级台阶为起点是两种方法；

1 + 1 + 2 = 4 种方法：

小孩走到四级台阶有七种走法：

以一级台阶为起点，是一种方法；

以二级台阶为起点，有两种方法；

以三级台阶为起点，有四种方法：

1 + 2 + 4 = 7 种方法：

现在是不是发现规律了，

实际上就是前面三个数相加。

2. 算法原理

1. 状态表示

根据我们之前学的，状态表示就是指：dp[ i ] 表示的是什么？

而 dp[ i ] 表示的是：到达 i 位置时，一共有多少种走法。

2. 状态转移方程

那么 dp[ i ] 等于什么呢？

根据前面找到规律，我们不难得出：

dp[ i ] = dp[ i - 3 ] + dp[ i - 2 ] + dp[ i - 1 ]

3. 初始化

初识化就靠我们自己刚刚算的：

dp[ 1 ] = 1，dp[ 2 ] = 2，dp[ 3 ] = 4。

4. 填表顺序

一步步上台阶，就是从左往右填。

5. 返回值

返回的就是 dp[ n ] 位置的值

3. 代码编写

代码编写其实就是按照我们之前的分析，

用固定的套路编写就行：

class Solution {
public:
    int waysToStep(int n) {
        // dp 题目的固定写代码套路
        // 1. 创建dp表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        const int MOD = 1e9 + 7;
        //考虑边界问题
        if(n == 1 || n == 2) return n;
        if(n == 3) return 4;
        vector 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];
    }
};

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~