算法——动态规划

1. 什么是动态规划？

动���规划（Dynamic Programming）是一种解决多阶段决策问题的优化方法。它通常用于解决具有重叠子问题和最优子结构性质的问题，能够将一个大问题分解为多个重叠的子问题，并通过存储子问题的解来避免重复计算，从而提高算法效率。

动态规划的基本思想是将原问题分解为若干子问题，先求解子问题的解，然后将这些子问题的解组合起来，逐步推导出原问题的解。为了避免重复计算，动态规划算法通常采用表格（数组）来存储已经求解的子问题的解，这种表格通常称为动态规划(dp)表。 

2. 动态规划算法的解题流程

动态规划算法的一般步骤如下：

1. 定义状态： 明确定义问题的状态，将原问题转化为具有重叠子问题的子问题。在解题中体现为确认dp表中每一个格子表示什么。

2. 找到状态转移方程： 建立子问题之间的递推关系，通过状态转移方程描述问题的最优子结构。在解题中体现为dp表如何去填写。

3. 初始化： 初始化动态规划表，将边界状态的值填入表中。在解题中，初始化的目的是为了保证最后得到的结果是正确的。

4. 逐步计算： 从边界状态开始，按照状态转移方程逐步计算并填充动态规划表。在解题中，体现为确认填dp表的方向。

5. 解读结果： 根据动态规划表中的结果得到原问题的解。在解题中，体现为返回正确结果。

3. 应用实例

①斐波那契数列模型

1. 第N个泰波那契数

题目链接：1137. 第 N 个泰波那契数 - 力扣（LeetCode）

解析：看完这道题，我们分析这个题目可以发现，题目已经将几乎动态规划的所有步骤告诉了我们，我们只需要按照他说的完成流程即可，我们定义dp[i]表示第i个泰波那契数，我们的动态转移方程为 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]，而初始化要想得到正确结果，我们需要将dp[0] = 0, dp[1] = dp[2] = 1，填表方向则是从左向右从第3个位置开始填，最后返回dp[n]即可（n为0,1,2时需要进行特殊判断），代码如下

class Solution {public:    int tribonacci(int n)     {        if (n == 0) return 0;        if (n