1. 什么叫路径类动态规划
路径类动态规划是动态规划的一个重要分支，核心解决'从起点到终点的路径相关问题'——比如'路径总数''最短路径长度''路径上的最大/最小和'等，其本质是通过'状态递推'避免重复计算，高效求解多阶段决策的路径问题。
核心定义（通俗理解）
把问题想象成'走迷宫'：
- 起点：初始状态（如网格的左上角）；
- 终点：目标状态（如网格的右下角）；
- 路径：从起点到终点的每一步选择（如只能向右/向下走）；
- 约束条件：每一步的限制（如不能走障碍物、只能走特定方向）；
- 目标：求路径的数量、最短距离、最大收益等。
动态规划的核心是'记住每一步的结果'：比如走到网格的 (i,j) 位置时，已有的路径数/最短距离，后续计算无需重复推导，直接基于前面的结果递推。
PS:一般来说，路径类的问题不仅可以用动态规划，还可以使用 BFS 和 DFS。
核心特征（识别这类问题的关键）
- 无后效性：走到 (i,j) 的路径只和'之前的步骤'有关，和'之后的步骤'无关（比如走到 (i,j) 有 5 条路径，不管之后怎么去终点，这 5 条路径的数量是固定的）；
- 重叠子问题：从起点到不同位置的路径会重复经过某些中间状态（比如走到 (i,j) 可能需要先经过 (i-1,j) 或 (i,j-1)，这两个状态的路径数需要反复用到）；
- 最优子结构：如果求'最短路径'，那么走到 (i,j) 的最短路径，一定是从 (i-1,j) 或 (i,j-1) 的最短路径中选更优的那个（子问题的最优解能推出原问题的最优解）。
2. 动态规划步骤
状态表示
状态表示就是我们数组对应的那个位置的值的含义，简单来说就是那个值代表着什么。比如说我们前面说的前缀和，那他的状态表示就是代表着原数组前面这些数的累加。
状态转移方程
状态转移方程就是根据上面的状态表示来得到的一个公式，比如说我们前面说的前缀和，它的状态转移方程就是 dp[i]=dp[i-1]+nums[i]。
初始化
初始化的作用简单来说就是为了防止数组越界访问，所以我们在一开始会给 dp 表的一小部分值提前给好。方便我们后续计算。拿前缀和来说就是第 0 个位子我们会直接给 0。
填表顺序
之所以我们要有填表顺序，是因为我们填当前位置的值会使用到前面的一些值，那么我们要确保前面的这些值都已经计算好了。
返回值
返回值就是返回题目要求的那个值。
3. 例题讲解
3.1 LeetCode 62. 不同路径
我们来看这道题，题目就是要求我们在一个二维数组里面，计算机器人从左上角走到右下角的路径总数。
所以在这道题里面它的状态表示就是走到当前位置的路线数。
所以在这道题里面它的状态转移方程就是 dp[i][j]=dp[i-1][j]+dp[i][j-1];
说明:我们在这里需要明白为什么是相加，这是因为题目里面说到达这个位置的方式只有上面和右边，那么我们到达该位置的数量就是这两个位置的相加。
我们在这边需要多设置一行一列，它的初始化就是在把虚拟位置的 [0][1] 给设置为 1.
说明：这边之所以这么设置是因为当前位是需要它上面的和左边的值。如果不这样设置的话，就会发生越界访问。（当然我们也可以不设置，直接把原本的第 0 行和第 0 列全部设置为 1，这样也是可以的。但是不推荐这样写，因为现在这些题目都是简单题，如果遇到一些难的题目的话，就会理不清了，所以建议还是多设置一行一列）
填表顺序就是一行一行的填写。
返回值就是 dp[m][n]。
{
:
{
vector<vector<>> (m,<>(n));
dp[][]=;
( i=;i<=m;++i) {
( j=;j<=n;++j) {
dp[i][j]=dp[i][j]+dp[i][j];
}
}
dp[m][n];
}
};
