【动态规划算法】专题二：路径问题解析与LeetCode实战
原文地址: https://88box.top 生成时间: 2026-05-21 01:02:03
【动态规划算法】专题二——路径问题 - hey99 知识搜索引擎
精选文章
【动态规划算法】专题二——路径问题
复习解题思路复习解题思路在使用这两个方法去寻找状态表示的时候，其中一个方法无法由此推导出正确的状态转移方程时，不用怀疑，就是这个状态表示压根就不对，换另一个方法。
更新于 2026-05-20 16:47
算法
leetcode
动态规划
职场和发展
数据结构
文章目录
前言
一、下降路径最小和
解题思路
代码实现及解析
总结
二、地下城游戏
解题思路
代码实现及解析
总结
前言
识别是不是dp问题
信号类型
题目中会出现的原话
本质原因
求最值
最大/最小/最多/最少/最长/最短/最高利润
最优子结构：全局最优解一定包含子问题的最优解
求方案数
有多少种方法/路径/组合/选择/可能性
重叠子问题：不同路径会走到同一个子问题
求可行性
能不能/是否可以/是否存在一种方式
状态可递推：当前状态由前序状态决定
隐含顺序性
只能从左到右/从上到下/前i个/前n步
无后效性：一旦状态确定，就不受后续决策影响
一、下降路径最小和
Leetcode链接
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
示例：
解题思路
使用“寻找递归子问题”的方法可以很好地找出dp问题的解题思路，类似于上个专题，在本题中可以发现从某一（最佳）起点到(i,j)位置的最小路径和=min( 到(i-1,j)位置的最小路径和，到(i-1,j-1)位置的最小路径和，到(i-1,j+1)位置的最小路径和) + (i,j)位置的值，这就是状态转移方程。那么状态表示：dp[i][j]表示从某一（最佳）起点到(i-1,j-1)位置的最小路径和（因为要进行dp表的扩展）
那么就只剩下关键的：初始化dp表—>解决边界情况了，本题非常具有代表性，我们发现要初始化的包括了：第0行、第0列、最后一列，而且对于这些边界位置我们无法手动进行初始化（无法提前计算），所以只能采取“扩展dp表来规避边界问题”的方法解决
由于dp[i][j]的计算需要其正上方、左上角、右上角这三个位置值的参与，所以我们要对dp表进行左、右两列+上面一行的扩展：
这时候就需要判断这些新扩展出来的位置是否需要手动赋值，而本题则再次强调了这些位置的赋值绝不是想当然的，而是分析出来的，那么经分析：第0行需要全部赋值为0（因为第1行的那些位置会受到它们的影响），而左、右两行则需要赋值为+∞，也就是
Integer.MAX_VALUE
（因为其临近的那一列会受到它们的影响）
代码实现及解析
class
Solution
{
public
int
minFallingPathSum
(
int
[
]
[
]
matrix
)
{
int
m
=
matrix
.
length
,
n
=
matrix
[
0
]
.
length
;
int
[
]
[
]
dp
=
new
int
[
m
+
1
]
[
n
+
2
]
;
//扩展dp表，以便处理边界位置
//状态表示：dp[i][j]表示从某一（最佳）起点到(i-1,j-1)位置的最小路径和
//初始化边界位置（第0行初始化为0，不用再处理了）：
for
(
int
i
=
1
;
i
<
m
+
1
;
i
++
)
{
dp
[
i
]
[
0
]
=
Integer
.
MAX_VALUE
;
//第0列初始化为+∞（从第二个元素开始）
dp
[
i
]
[
n
+
1
]
=
Integer
.
MAX_VALUE
;
//最后一列初始化为+∞（从第二个元素开始）
}
//填表：
for
(
int
i
=
1
;
i
<
m
+
1
;
i
++
)
{
for
(
int
j
=
1
;
j
<
n
+
1
;
j
++
)
{
dp
[
i
]
[
j
]
=
Math
.
min
(
Math
.
min
(
dp
[
i
-
1
]
[
j
]
,
dp
[
i
-
1
]
[
j
-
1
]
)
,
dp
[
i
-
1
]
[
j
+
1
]
)
+
matrix
[
i
-
1
]
[
j
-
1
]
;
//状态转移方程
}
}
//找出最后一行中的最小路径和：
int
ret
=
Integer
.
MAX_VALUE
;
for
(
int
j
=
1
;
j
<
n
+
1
;
j
++
)
{
ret
=
Math
.
min
(
ret
,
dp
[
m
]
[
j
]
)
;
}
return
ret
;
}
}
总结
复习解题思路
二、地下城游戏
Leetcode链接
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
解题思路
上个专题中我们说了，寻找状态表示有两种方法：
方法一（从固定的起点到变化的终点），也就是：以某位置为起点…
方法二（从变化的起点到固定的终点），也就是：以某位置为终点…
而本题的所用的方法则有所取舍：
错误方法（方法一）：
如果设计dp[i][j]表示从起点开始到(i,j)位置所需的最低起始血量，那么是无法推导出正确的状态转移方程的：
如果想当然的以为dp(30)=min( dp(-10) , dp(10) )-dungeon(30) 的话就错了，你看这个时候减完dungeon(30)，得出的结果是在-5位置的最低血量反而要减小，因为在数学计算上确实走到30位置吃了这个血包之后血量会＞0，但是按游戏逻辑，中间任意时刻血量都不能<=0，而方法一的策略仅仅保证了走到最后不<=0
所以这个时候就要换方法二进行尝试：
方法二
我们设计状态表示为：dp[i][j]表示从(i,j)位置开始到终点所需的最低初始血量值，那么我们可以得出这样的状态转移方程：
dp[i][j]=Math.min(dp[i][j+1],dp[i+1][j])-dungeon[i][j]
，这样的话就是往前填表，得出的结果就是正确的。
当然这个方法在往前填表时也会出现遇见一个大血包，然后减去这个血包值之后dp[i][j]突然变为了负数（符合数学计算，但不符合游戏逻辑），此时对于这种情况，我们只需手动将其更改为1（最小的正整数）就行了，这样往后走肯定没问题，我们就是从后面往前填表走来的，往前走去填表依然有这个计算逻辑撑腰
初始化问题照常去判断
代码实现及解析
class
Solution
{
public
int
calculateMinimumHP
(
int
[
]
[
]
dungeon
)
{
int
m
=
dungeon
.
length
,
n
=
dungeon
[
0
]
.
length
;
int
[
]
[
]
dp
=
new
int
[
m
+
1
]
[
n
+
1
]
;
//状态表示：dp[i][j]表示从(i,j)位置开始到终点所需的最低初始血量值（因为这次是在dp表的下方进行扩展，所以下标的一一映射不用改变）
//dp表的初始化：
for
(
int
i
=
0
;
i
<
m
-
1
;
i
++
)
dp
[
i
]
[
n
]
=
Integer
.
MAX_VALUE
;
for
(
int
j
=
0
;
j
<
n
-
1
;
j
++
)
dp
[
m
]
[
j
]
=
Integer
.
MAX_VALUE
;
dp
[
m
-
1
]
[
n
]
=
dp
[
m
]
[
n
-
1
]
=
1
;
//填表（从后往前）：
for
(
int
i
=
m
-
1
;
i
=
0
;
i
--
)
{
for
(
int
j
=
n
-
1
;
j
=
0
;
j
--
)
{
int
tmp
=
Math
.
min
(
dp
[
i
]
[
j
+
1
]
,
dp
[
i
+
1
]
[
j
]
)
-
dungeon
[
i
]
[
j
]
;
//状态转移方程
dp
[
i
]
[
j
]
=
Math
.
max
(
tmp
,
1
)
;
//重要细节：如果发现经数学计算，该位置需要的最低血量tmp为负数，但按照游戏逻辑，我们肯定要手动改为正整数的
}
}
return
dp
[
0
]
[
0
]
;
}
}
总结
复习解题思路
在使用这两个方法去寻找状态表示的时候，其中一个方法无法由此推导出正确的状态转移方程时，不用怀疑，就是这个状态表示压根就不对，换另一个方法
查看原文
🏷 标签: 动态规划, 路径问题, LeetCode, 算法优化, 数组DP