动态规划做题步骤：
-
状态表示：dp表中每一个格子所表示的意义。
-
状态转移方程：dp[i] 等于什么。
-
初始化：保证填表不越界。
-
填表顺序：为了填写当前格子，它需要的数据已经准备好。
-
返回值：根据题目要求和状态表示返回结果。
第n个泰波那契数：
链接：https://leetcode.cn/problems/n-th-tribonacci-number/
题目描述：泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
示例1：
输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
点击查看代码
public int tribonacci(int n) {
// 状态表示：dp[i] 表示：返回的第i个泰波那契数的值
// 状态方程：dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1]
// 初始化: dp[0] = 0; dp[1] = dp[2] = 1
// 填表顺序: 从左往右
// 返回值: dp[n]
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
int[] dp = new int[n + 1];
dp[1] = dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
}
return dp[n];
}
三步问题：
链接：https://leetcode.cn/problems/three-steps-problem-lcci/
题目描述：三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
示例1：
输入：n = 3
输出：4
说明: 有四种走法
点击查看代码
public int waysToStep(int n) {
// 状态表示: dp[i]:表示小孩上到第i阶台阶的上楼梯方式
// 状态转移方程: dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
// 初始化: dp[1] = 1; dp[2] = 2; dp[3] = 4;
// 填表顺序: 从左往右
// 返回值: dp[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];
}
使用最小花费爬楼梯：
链接：https://leetcode.cn/problems/min-cost-climbing-stairs/
题目描述：给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。支付 15 ，向上爬两个台阶，到达楼梯顶部。总花费为 15 。
点击查看代码
public int minCostClimbingStairs(int[] cost) {
// 状态表示: dp[i]: 到达第i阶台阶的最低花费
// 状态方程: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
// 初始化: dp[0] = 0; dp[1] = 0;
// 填表顺序: 从左往右
// 返回值: dp[n]
int n = cost.length;
if (n == 0 || n == 1) return 0;
int[] dp = new int[n+1];
for (int i = 2; i <= n; i++){
dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
}
return dp[n];
}