【动态规划】
1、三步问题 - 力扣（LeetCode）
- 算法原理：
1、题目解析
小孩每次可以上1个台阶、两个台阶、三个台阶；
当只有一个台阶的时候只有一种方式
当有两个台阶的时候，有两种方式
当有三种台阶的时候，三种上法都可以使用，此时有四种方式
2、状态转移方程
当到了i位置的时候，与其最近的位置就是i-1，i-2，i-3，通过这三步来划分问题
3、初始化
根据题意，有三种上楼梯方式，所以给前三个初始化
dp[1] = 1
dp[2] = 2
dp[3] = 4
4、填表顺序：从左往右
5、返回值
返回n位置的方法数，即：dp[n]
代码：
class Solution {//1、创建 dp 表//2、初始化//3、填 dp 表//4、返回值public int waysToStep(int n) {//结果取模int MOD = (int)1e9 + 7;//处理一下边界情况if(n == 1 || n == 2){return n;}if(n == 3){return 4;}int[] dp = new int[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];}
}