一、动态规划解题模版
- 状态表示：一般创建一维数组 dp，把 dp 表填满，其中的某一个值就是结果。状态表示指 dp 表中元素的含义。 1.1. 来源：题目要求、经验 + 题目要求，分析问题的过程中的重复子问题
- 状态转移方程：dp[i] = ?
- 初始化：保证根据状态转移方程填表时不越界
- 填表顺序：为了填写当前状态的时候，所需要的状态已经计算过了
- 返回值：题目要求 + 状态表示
二、第 N 个泰波那契数
题目：第 N 个泰波那契数
题目描述：第四个数是前三个数的和，第一二三个数定为 0 1 1，返回第 n 个数。
题目解析：
解题思路：
- 状态表示：dp[i] 表示第 i 个泰波那契数
- 状态转移方程：dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
- 初始化：dp[0] = 0, dp[1] = 1, dp[2] = 1
- 填表顺序：顺序从左向右填表即可
- 返回值：dp[n]
解题代码：
// 时间复杂度：O(N)
// 空间复杂度：O(N)
class Solution {
public int tribonacci(int n) {
if (n < 3) return n == 0 ? 0 : 1;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = dp[2] = 1;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
return dp[n];
}
}
空间优化：只创建长度为三的数组即可：
// 时间复杂度：O(N)
// 空间复杂度：O(1)
{
{
(n < ) n == ? : ;
[] dp = []{, , };
( ; i <= n; i++) {
dp[];
dp[] = dp[];
dp[] = dp[];
dp[] = tmp + dp[] + dp[];
}
dp[];
}
}