动态规划——路径问题

feng_qi0325

1274人浏览 · 2025-03-30 09:52:14

feng_qi0325 · 2025-03-30 09:52:14 发布

2.动态规划——路径问题

动态规划思路是一样：

确定状态表示
列写状态方程
填表顺序
初始化
返回值

其中最重要的就是确定状态表示以及列写状态方程，其中列写状态方程是根据相邻位置找经验获得的

不同路径

题目链接：

不同路径

要点：

状态定义：dp[i][j] 表示到达 (i,j) 位置的路径数
状态转移：dp[i][j] = dp[i-1][j] + dp[i][j-1]
虚拟节点：通过 dp[0][1] = 1 简化初始化

老师代码：

class Solution
{
public:
    int uniquePaths(int m, int n)
    {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 创建⼀个 dp表
        dp[0][1] = 1; // 初始化
        // 填表
        for (int i = 1; i <= m; i++) // 从上往下
            for (int j = 1; j <= n; j++) // 从左往右
                p[i][j] = dp[i - 1][j] + dp[i][j - 1];
        // 返回结果
        return dp[m][n];
    }
}

老师思路：

状态表⽰：对于这种「路径类」的问题，我们的状态表⽰⼀般有两种形式：

i. 从 [i, j] 位置出发，巴拉巴拉；
ii. 从起始位置出发，到达 [i, j] 位置，巴拉巴拉。

这⾥选择第⼆种定义状态表⽰的⽅式：dp[i] [j] 表⽰：⾛到 [i, j] 位置处，⼀共有多少种⽅式。

状态转移⽅程：简单分析⼀下。如果 dp[i] [j] 表⽰到达 [i, j] 位置的⽅法数，那么到达 [i, j] 位置之前的⼀⼩步，有两种情况：i. 从 [i, j] 位置的上⽅（ [i - 1, j] 的位置）向下⾛⼀步，转移到 [i, j] 位置； ii. 从 [i, j] 位置的左⽅（ [i, j - 1] 的位置）向右⾛⼀步，转移到 [i, j] 位置。由于我们要求的是有多少种⽅法，因此状态转移⽅程就呼之欲出了： dp[i][j] = dp[i - 1] [j] + dp[i] [j - 1] 。
初始化：可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化。使⽤这种技巧要注意两个点：

i. 辅助结点⾥⾯的值要「保证后续填表是正确的」；
ii. 「下标的映射关系」。

在本题中，「添加⼀⾏」，并且「添加⼀列」后，只需将 dp[0] [1] 的位置初始化为 1 即可

填表顺序：根据「状态转移⽅程」的推导来看，填表的顺序就是「从上往下」填每⼀⾏，在填写每⼀⾏的时候「从左往右」。
返回值：根据「状态表⽰」，我们要返回 dp[m] [n] 的值。

我的代码：

class Solution {
    vector<vector<int>> memo;//存放走到[i, j] 位置时有多少
public:
    int uniquePaths(int m, int n) {
        memo = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));//全部初始化为-1表示还没有填入数据     
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                memo[i][j] = memo[i - 1][j] + memo[i][j - 1];
                if(i == 1 && j == 1) memo[i][j] = 1;
            }
        }
        return memo[m][n];
    }
};

我的思路：

这个题目其实在递归专题的记忆化搜索中已经写过了，这和记忆化搜索的方法还是很像的，只不过记忆化搜索用的是递归，这里用的是循环+动态规划

添加虚拟行和列，避免处理 i=0 或 j=0 的边界
填表顺序从上到下、从左到右，保证计算时前驱状态已确定
时间复杂度 O(mn)，空间复杂度可优化为 O(n)

不同路径II

题目链接：

不同路径

要点：

状态定义与基础版相同，但需跳过障碍格
转移方程：若 grid[i][j] 为障碍，dp[i][j] = 0

老师代码：

class Solution 
{
public:
    int uniquePathsWithObstacles(vector<vector<int>>& ob) 
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = ob.size(), n = ob[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[1][0] = 1;
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                if(ob[i - 1][j - 1] == 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m][n];
    }
};

老师思路：

本题为不同路径的变型，只不过有些地⽅有「障碍物」，只要在「状态转移」上稍加修改就可解决。

只要这个位置上「有障碍物」，那么我们就不需要计算这个位置上的值，直接让它等于 0 即可

我的代码：

class Solution 
{
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) 
    {
        int m = grid.size(), n = grid[0].size();
        if(grid[0][0] == 1) return 0;

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        dp[0 + 1][0 + 1] = 1;

        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(i == 1 && j == 1) continue;
                if(grid[i - 1][j - 1] == 0) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m][n];
    }
};

我的思路：

起点或终点为障碍时直接返回0
初始化时需判断首格是否为障碍
填表时遇到障碍格则保持为0

我的笔记:

虚拟节点技巧同样适用，但需注意原始网格的索引偏移
空间优化时需额外变量保存左方状态

珠宝的最高价值

题目链接：

珠宝的最高价值

要点：

状态定义：dp[i][j] 表示到达 (i,j) 时的最大价值
状态转移：dp[i][j] = max(上, 左) + grid[i][j]

老师代码：

class Solution
{
public:
    int maxValue(vector<vector<int>>& grid)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        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]) + grid[i - 1][j - 1];
        return dp[m][n];
    }
}

老师思路：

状态转移⽅程：

对于 dp[i][j] ，我们发现想要到达 [i, j] 位置，有两种⽅式：

i. 从 [i, j] 位置的上⽅ [i - 1, j] 位置，向下⾛⼀步，此时到达 [i, j] 位置能拿到的礼物价值为 dp[i - 1] [j] + grid[i] [j] ；

ii. 从 [i, j] 位置的左边 [i, j - 1] 位置，向右⾛⼀步，此时到达 [i, j] 位置能拿到的礼物价值为 dp[i] [j - 1] + grid[i] [j] 我们要的是最⼤值，

因此状态转移⽅程为：dp[i][j] = max(dp[i - 1] [j], dp[i][j - 1]) + grid[i] [j]

我的代码：

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size(), n = frame[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 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]) + frame[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
};

我的思路：

虚拟节点初始化为0，避免边界判断
直接从左上角递推至右下角

我的笔记:

空间优化可用滚动数组

下降路径最小和

题目链接：

下降路径最小和

要点：

状态定义：dp[i][j] 表示到达 (i,j) 的最小路径和
状态转移：dp[i][j] = min(左上, 正上, 右上) + matrix[i][j]

老师代码：

class Solution
{
public:
    int minFallingPathSum(vector<vector<int>>& matrix)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        int n = matrix.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
        // 初始化第⼀⾏
        for(int j = 0; j < n + 2; j++) dp[0][j] = 0;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
        int ret = INT_MAX;
        for(int j = 1; j <= n; j++)
            ret = min(ret, dp[n][j]);
        return ret;
    }
}

老师思路：

关于这⼀类题，由于我们做过类似的，因此「状态表⽰」以及「状态转移」是⽐较容易分析出来的。⽐较难的地⽅可能就是对于「边界条件」的处理

我的代码：

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& m) {
        int n = m.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 2, 10001));//在m大小的基础上，我们扩展上、左、右三边初始化为10001

        //初始化第一行为0
        for(int i = 0; i < n + 2; i++)
            dp[0][i] = 0;
        
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1])) + m[i - 1][j - 1];
            }
        int ret = dp[n][1];
        for(int i = 2; i <= n; i++)
            ret = min(ret, dp[n][i]);
        return ret;
    }
};

我的思路：

0	0	0	0	0	0
10001	有效数据	有效数据	有效数据	有效数据	10001
10001	有效数据	有效数据	有效数据	有效数据	10001
10001	有效数据	有效数据	有效数据	有效数据	10001
10001	有效数据	有效数据	有效数据	有效数据	10001
10001	有效数据	有效数据	有效数据	有效数据	10001

我的笔记:

主要要注意的就是防止数组越界——初始化时对dp表在原始数组的大小的基础上扩展上、左、右三边，其中上边初始化为0防止影响第一行dp表的值，左右边初始化为10001，因为根据题目要求，可知函数的返回值最大为10000
这种题目还是要画图的

最小路径和

题目链接：

最小路径和

要点：

状态定义：dp[i][j] 表示到达 (i,j) 的最小路径和
状态转移：dp[i][j] = min(上, 左) + grid[i][j]

老师代码：

class Solution
{
public:
    int minPathSum(vector<vector<int>>& grid)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        int m = grid.size(), n = grid[0].size();
        
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        
        dp[0][1] = dp[1][0] = 0;
        
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
        return dp[m][n];
    }
}

老师思路：

像这种表格形式的动态规划，是⾮常容易得到「状态表⽰」以及「状态转移⽅程」的，可以归结到「不同路径」⼀类的题⾥⾯

我的代码：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));//全部初始化为最大值
        //初始化
        dp[0][1] = dp[1][0] = 0;

        //填表
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }

        return dp[m][n];
    }
};

我的思路：

这个很简单，和之前的动态规划做法类似

初始化虚拟行和列为 INT_MAX，但 dp[0][1] = dp[1][0] = 0
直接递推填表，无需复杂边界处理

地下城游戏

题目链接：

地下城游戏

要点：

逆向DP：dp[i][j] 表示从 (i,j) 出发到终点的最低初始血量
状态转移：dp[i][j] = max(1, min(下, 右) - dungeon[i][j])

老师代码：

class Solution
{
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon)
    {
        int m = dungeon.size(), n = dungeon[0].size();
        // 建表 + 初始化
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m][n - 1] = dp[m - 1][n] = 1;
        // 填表
        for(int i = m - 1; i >= 0; i--)
            for(int j = n - 1; j >= 0; j--)
            {
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = max(1, dp[i][j]);
            }
        // 返回结果
        return dp[0][0];
    }
};

老师思路：

状态表⽰：这道题如果我们定义成：从起点开始，到达 [i, j] 位置的时候，所需的最低初始健康点数。那么我们分析状态转移的时候会有⼀个问题：那就是我们当前的健康点数还会受到后⾯的路径的影响。也就是从上往下的状态转移不能很好地解决问题。这个时候我们要换⼀种状态表⽰：从 [i, j] 位置出发，到达终点时所需要的最低初始健康点数。这样我们在分析状态转移的时候，后续的最佳状态就已经知晓。

综上所述，定义状态表⽰为：dp[i] [j] 表⽰：从 [i, j] 位置出发，到达终点时所需的最低初始健康点数
状态转移⽅程：对于 dp[i] [j] ，从 [i, j] 位置出发，下⼀步会有两种选择（为了⽅便理解，设 dp[i] [j] 的最终答案是 x ）：

i. ⾛到右边，然后⾛向终点那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗，应该要⼤于等于右边位置的最低健康点数，也就是： x + dungeon[i] [j] >= dp[i] [j + 1] 。通过移项可得： x >= dp[i] [j + 1] - dungeon[i] [j] 。因为我们要的是最⼩值，因此这种情况下的 x = dp[i] [j + 1] - dungeon[i] [j] ；
ii. ⾛到下边，然后⾛向终点那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗，应该要⼤于等于下边位置的最低健康点数，也就是： x + dungeon[i][j] >= dp[i + 1] [j] 。通过移项可得： x >= dp[i + 1] [j] - dungeon[i] [j] 。因为我们要的是最⼩值，因此这种情况下的 x = dp[i + 1] [j] - dungeon[i] [j] ；综上所述，我们需要的是两种情况下的最⼩值，
因此可得状态转移⽅程为：dp[i] [j] = min(dp[i + 1] [j], dp[i] [j + 1]) - dungeon[i] [j]但是，如果当前位置的 dungeon[i] [j] 是⼀个⽐较⼤的正数的话， dp[i] [j] 的值可能变成 0 或者负数。也就是最低点数会⼩于 1 ，那么骑⼠就会死亡。因此我们求出来的 dp[i] [j]如果⼩于等于 0 的话，说明此时的最低初始值应该为 1 。处理这种情况仅需让与 1 取⼀个最⼤值即可： dp[i] [j] = max(1, dp[i] [j])

初始化：可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化。使⽤这种技巧要注意两个点：

i. 辅助结点⾥⾯的值要「保证后续填表是正确的」；
ii. 「下标的映射关系」。在本题中，在 dp 表最后⾯添加⼀⾏，并且添加⼀列后，所有的值都先初始化为⽆穷⼤，然后让 dp[m] [n - 1] = dp[m - 1] [n] = 1 即可。

填表顺序：根据「状态转移⽅程」，我们需要「从下往上填每⼀⾏」，「每⼀⾏从右往左」。
返回值：根据「状态表⽰」，我们需要返回 dp[0] [0] 的值。

我的代码：

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));//从某一位置开始所需的最小血量
        dp[m][n - 1] = dp[m - 1][n] = 1;
        for(int i = m - 1; i >= 0; i--)
        {
            for(int j = n - 1; j >= 0; j--)
            {
                dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];//移动到下一个位置的最小血量减去当前需要消耗的血量
                if(dp[i][j] <= 0) dp[i][j] = 1;//如果小于或等于0，则表示后面不需要额外消耗血量，但必须保证骑士在进入这个位置之前血量至少为1
            }
        }
        
        return dp[0][0];
    }
};

我的思路：

从终点逆向计算，确保后续路径已知
末行末列初始化为极大值，终点右侧和下侧初始化为1

我的笔记:

正向DP难以处理后续路径依赖，逆向更优
关键方程：dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])

注意事项总结

C++语法相关：

二维数组初始化：

cpp

复制

vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); // 明确初始化值

边界处理：通过虚拟节点简化代码，注意原始索引偏移
溢出处理：用 INT_MAX 表示无效值，避免运算溢出

算法思路相关：

状态定义方向：
- 正向：适用于无后效性问题（如路径计数）
- 逆向：适用于后续路径影响当前决策（如地下城游戏）
空间优化：
- 滚动数组：将二维DP压缩为一维
- 反向填表：减少维度依赖

通用模板：

1. 定义状态（含虚拟节点）
2. 初始化边界
3. 按顺序填表
4. 处理特殊约束（障碍、最小值限制）
5. 返回目标状态

常见陷阱：

未处理起点或终点为障碍的情况
反向DP时未正确初始化终点相邻位置
二维数组索引混淆（尤其含虚拟节点时）

天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能