三步问题 --- 动态规划

目录

一：题目

二：算法原理

三：代码实现

一：题目

题目链接：面试题 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;//1.创建dp表vector<int> dp(n+1);//2.初始化dp[1] = 1,dp[2] =2,dp[3] =4;//3.填表for(int i = 4;i <=n; i++)dp[i] = ((dp[i-1]+dp[i-2])%MOD+dp[i-3])%MOD;//4.返回值return dp[n];}
};