一、题目解析

 

此题可以类比第N个泰波那契数

二、算法解析

 1、状态表示

根据上面的分析和题目要求，dp[i]表示：到达i位置，一共有多少种方法

2、状态转移方程

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

dp[i]   从i-1->i  dp[i-1]

          从i-2->i  dp[i-2]

          从i-3->i  dp[i-3]

 

3、初始化

计算四节台阶的方法需要前三阶各自的方法数，所以初始化dp[1] = 1,dp[2] = 2,dp[3] = 4

4、填dp表的顺序

以4为起点，从左往右依次填写

5、返回值

根据题目要求需要返回在i点的方法数，所以返回dp[n]

小细节：

题目上说数字会过大所以需要模上一个10000000007，也就是1e9+7

老规矩，先去自己实现结合解析，链接：面试题 08.01. 三步问题 - 力扣（LeetCode）

三、代码示例

class Solution {
public:int waysToStep(int n) {const int MOD = 1e9 + 7;//定义模数if(n == 1 || n == 2) return n;//处理边界条件if(n == 3) return 4;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-1] + dp[i-2]) % MOD + dp[i-3]) % MOD;//对两个加法分别取模}return dp[n];//返回结果}
};

 

 四、空间优化

该题空间优化与第N个泰波那契数类似，如果感兴趣的朋友可以去看看我之前的博客

链接：动态规划-1137.第N个泰波那契数-力扣(LeetCode)-CSDN博客

看到最后，如果对您有所帮助还请留下免费的赞和收藏，我们下期再见！