1. 三步问题
题目链接：
面试题 08.01. 三步问题 - 力扣（LeetCode）https://leetcode.cn/problems/three-steps-problem-lcci/description/
2. 题目解析
本题要求小孩可以一次性跨1 / 2 /3个台阶 ，由图可以看出0到1有一种方法，0到2有跨一步（直接到2）和跨两步（先到1再到2）两种方法，0到3有跨一步（直接到3）和跨两步（先到1再到3），跨两步（先到2再到3），跨3步（先到1再到2再到3）四种方法
到第四个台阶的位置时0就不能过去了，那么就要先到1再到4（第一种方法），当到了第一个台阶时那么情况就和之前的从第0个台阶到第3给台阶有几步相同，也就是：1+2+4=7
从这里就看出来后面的台阶就等于前3个台阶的次数相加
3. 算法原理
1. 状态表示：以i位置为结尾
dp[i]表示：到达第i个位置的时候，一共有多少种方法
2. 状态转移方程：以i位置的状态，最近的一步来划分情况
dp[i]分为3种情况来表示：
1. 从dp[i-1]到dp[i]
2. 从dp[i-2]到dp[i]
3. 从dp[i-3]到dp[i]
本题的状态转移方程是：dp[i]=dp[i-1] + dp[i-2] + dp[i-3]
3. 初始化：把dp表填满不越界，让后面的填表可以顺利进行
如何填表：就是根据前面的状态转移方程来进行填表
本题的题目并没有直接说明前三个初始化是多少，但是我们根据前面的推导可以得出本题的初始化为：dp[1] = 1 dp[2] = 2 dp[i-3] = 4
4. 填表顺序
本题的填表顺序是：从左到右
5. 返回值 ：题目要求 + 状态表示
本题的返回值是：直接返回dp[n]
4. 代码
动态规划的固定四步骤：1. 创建一个dp表
2. 在填表之前初始化
3. 填表（填表方法：状态转移方程）
4. 确定返回值
普通版本，适用于数据不大的情况
class Solution {
public:int waysToStep(int n) {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] + dp[i - 3];return dp[n];}
};加上取模（%）版本，方便使用更大的数据
class Solution {
public:const int MOD = 1e9+7;int waysToStep(int n) {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];}
};
完结撒花~