【动态规划专栏】专题一：斐波那契数列模型--------2.三步问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了【动态规划专栏】专题一：斐波那契数列模型--------2.三步问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。通过本专栏的深入学习，你可以了解并掌握算法。

💓博主csdn个人主页：小小unicorn
⏩专栏分类：动态规划专栏
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

题目来源

本题来源为：

Leetcode面试题 08.01. 三步问题

题目描述

三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
【动态规划专栏】专题一：斐波那契数列模型--------2.三步问题,算法专栏,# 动态规划算法专栏,动态规划,算法,c++

题目解析

【动态规划专栏】专题一：斐波那契数列模型--------2.三步问题,算法专栏,# 动态规划算法专栏,动态规划,算法,c++
我们模拟一下小孩上楼梯的过程，会很容易发现规律

算法原理

1.状态表示

经验+题目要求

而经验就是：以i位置为结尾+…
（对一维的dp而言，基本上就是两种：以i位置为结尾+…或者以i位置为开始+…）

…表示根据题目要求进行补充完整。

对于本题而言：
【动态规划专栏】专题一：斐波那契数列模型--------2.三步问题,算法专栏,# 动态规划算法专栏,动态规划,算法,c++

dp[i] 表示:到达i位置时,一共有多少种方法

2.状态转移方程

在推导时基本上就是：

以i位置的状态，最近的一步，来划分问题

对于本题而言：到达i位置需要分三种情况
【动态规划专栏】专题一：斐波那契数列模型--------2.三步问题,算法专栏,# 动态规划算法专栏,动态规划,算法,c++
因此状态方程为：

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]文章来源地址https://www.toymoban.com/news/detail-834471.html

代码实现

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];
        
    }
};