算法王冠上的明珠——动态规划之路径问题(第一篇）
目录
今天我们来聊一聊动态规划的路径类问题。
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 LeetCode62. 不同路径
我们来看这道题，题目就是要求我们在一个二维数组里面，计算机器人从左上角走到右下角的路径总数。
所以在这道题里面它的状态表示就是走到当前位置的路线数。
所以在这道题里面它的状态转移方程就是dp[i][j]=dp[i-1][j]+dp[i][j-1];
PS:我们在这里需要明白为什么是相加，这是因为题目里面说到达这个位置的方式只有上面和右边，那么我们到达该位置的数量就是这两个位置的相加。
我们在这边需要多设置一行一列，它的初始化就是在把虚拟位置的[0][1]给设置为1.
PS:这边之所以这么设置是因为当前位是需要它上面的和左边的值。如果不这样设置的话，就会发生越界访问。（当然我们也可以不设置，直接把原本的第0行和第0列全部设置为1，这样也是可以的。但是不推荐这样写，因为现在这些题目都是简单题，如果遇到一些难的题目的话，就会理不清了，所以建议还是多设置一行一列）
填表顺序就是一行一行的填写。
返回值就是dp[m][n]。
class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(m+1,vector<int>(n+1)); dp[0][1]=1; for(int i=1;i<=m;++i) { for(int j=1;j<=n;++j) { dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[m][n]; } };3.2 LeetCode63. 不同路径 II
这道题目的话和上面那一道题目很像，都是在一个二维数组里面，计算机器人从左上角走到右下角的路径总数。唯一的区别就是这道题给的数组里面是存在石头的，也就是需要机器人绕路的点。
所以在这道题里面它的状态表示就是走到当前位置的路线数。
所以在这道题里面它的状态转移方程就是dp[i][j]=dp[i-1][j]+dp[i][j-1]，如果遇到石头的话就是0。
我们在这边需要多设置一行一列，它的初始化就是在把虚拟位置的[0][1]给设置为1.
填表顺序就是一行一行的填写。
返回值就是dp[m][n]。
class Solution { public: int uniquePathsWithObstacles(vector<vector<int>>& ob) { int m=ob.size(); int n=ob[0].size(); vector<vector<int>> dp(m+1,vector<int>(n+1)); dp[0][1]=1; for(int i=1;i<=m;++i) { for(int j=1;j<=n;++j) { if(ob[i-1][j-1]==1) dp[i][j]=0; else dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[m][n]; } };3.3 LeetCodeLCR 166. 珠宝的最高价值
这道题的话和前面两道题目不太一样，题目是要求我们到达右下角时整个途中经过的数组数字和最大。
这道题的话是带着一点贪心的思想在里面的，我们在设计代码的时候也是同样的，就是要让dp表里面的每一个位置都是代表走到这个位置时所能达到的最大值。
所以在这道题里面它的状态表示就是走到当前位置时能达到的最大值。
所以在这道题里面它的状态转移方程就是dp[i][j]=max(dp[i-1][j],dp[i][j-1])+f[i-1][j-1]。
（+f[i-1][j-1]是因为还需要加上当前位置的值，也就是走到这个位置时的自身值）
我们在这边需要多设置一行一列，它的初始化就是在把虚拟位置的[0][1]给设置为1.
填表顺序就是一行一行的填写。
返回值就是dp[m][n]。
class Solution { public: int jewelleryValue(vector<vector<int>>& f) { int m=f.size(); int n=f[0].size(); vector<vector<int>> dp(m+1,vector<int>(n+1,0)); dp[1][1]=f[0][0]; for(int i=1;i<=m;++i) { for(int j=1;j<=n;++j) { dp[i][j]=max(dp[i-1][j],dp[i][j-1])+f[i-1][j-1]; } } return dp[m][n]; } };
