1. 什么是动态规划
动态规划是一种通过将复杂问题分解为重叠子问题，并利用子问题的解来高效求解原问题的算法思想。它的核心是避免重复计算，通过存储中间结果（即'记忆化'）来优化时间复杂度。
简单来说，就是通过前面的状态来定义后面的状态。例如前缀和问题也可视为一种简单的动态规划，通常归类于基础算法中。
2. 动态规划步骤
做动态规划类题目的步骤如下：
状态表示
状态表示就是数组对应位置值的含义，即该值代表什么。例如前缀和的状态表示就是原数组前面这些数的累加。
状态转移方程
状态转移方程是根据状态表示得到的公式。例如前缀和的状态转移方程为 dp[i] = dp[i-1] + nums[i]。
初始化
初始化的作用是防止数组越界访问，提前给 DP 表的一小部分值赋值，方便后续计算。例如前缀和中第 0 个位置直接设为 0。
填表顺序
填表顺序需确保计算当前位置的值时，所需的前置值已经计算完成。
返回值
返回值即题目要求的结果。
3. 例题讲解及具体代码
3.1 LeetCode 1137. 第 N 个泰波那契数
题目要求当前位置的值由前面三个位置的值决定。
- 状态表示：当前位置值等于前面三个位置的值的和。
- 状态转移方程：
dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。 - 初始化：第 0 个位置设为 0，第 1、2 个位置设为 1。
- 填表顺序：从前往后。
- 返回值：第 n 个位置的值。
基于上述步骤，代码实现如下：
class Solution {
public:
int tribonacci(int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
vector<int> dp(n + );
dp[] = ;
dp[] = ;
dp[] = ;
( i = ; i <= n; ++i) {
dp[i] = dp[i - ] + dp[i - ] + dp[i - ];
}
dp[n];
}
};
