【动态规划】

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

2、使用最小花费爬楼梯 - 力扣（LeetCode）