【C++动态规划】2304. 网格中的最小路径代价|1658
本文涉及知识点
LeetCode2304. 网格中的最小路径代价
给你一个下标从 0 开始的整数矩阵 grid ，矩阵大小为 m x n ，由从 0 到 m * n - 1 的不同整数组成。你可以在此矩阵中，从一个单元格移动到 下一行 的任何其他单元格。如果你位于单元格 (x, y) ，且满足 x < m - 1 ，你可以移动到 (x + 1, 0), (x + 1, 1), …, (x + 1, n - 1) 中的任何一个单元格。注意： 在最后一行中的单元格不能触发移动。
每次可能的移动都需要付出对应的代价，代价用一个下标从 0 开始的二维数组 moveCost 表示，该数组大小为 (m * n) x n ，其中 moveCost[i][j] 是从值为 i 的单元格移动到下一行第 j 列单元格的代价。从 grid 最后一行的单元格移动的代价可以忽略。
grid 一条路径的代价是：所有路径经过的单元格的 值之和 加上 所有移动的 代价之和 。从 第一行 任意单元格出发，返回到达 最后一行 任意单元格的最小路径代价。
示例 1：
输入：grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
输出：17
解释：最小代价的路径是 5 -> 0 -> 1 。
- 路径途经单元格值之和 5 + 0 + 1 = 6 。
- 从 5 移动到 0 的代价为 3 。
- 从 0 移动到 1 的代价为 8 。
路径总代价为 6 + 3 + 8 = 17 。
示例 2：
输入：grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]
输出：6
解释：
最小代价的路径是 2 -> 3 。
- 路径途经单元格值之和 2 + 3 = 5 。
- 从 2 移动到 3 的代价为 1 。
路径总代价为 5 + 1 = 6 。
提示：
m == grid.length
n == grid[i].length
2 <= m, n <= 50
grid 由从 0 到 m * n - 1 的不同整数组成
moveCost.length == m * n
moveCost[i].length == n
1 <= moveCost[i][j] <= 100
动态规划
动态规划的状态表示
dp[r][c] 记录第一行任意单格到(r,c)的最小代价。空间复杂度：O（mn）
pre = dp[r]
cur= dp[r+1]
动态规划的转移方程
枚举前置状态，更新后序状态。
MinSelf(cur[j],pre[c] +move[grid[r][c]][j] + grid[r+1][j])
动态规划的填报顺序
for i = 0 To m-1
动态规划的初始值
dp[0] = grid[0]，其它全部是INT_MAX
动态规划的返回值
dp.back()的最小值
代码
核心代码
class Solution {
public:
int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
const int R = grid.size();
const int C = grid[0].size();
vector<int> pre = grid[0];
for (int r = 0; r + 1 < R; r++) {
vector<int> dp(C, INT_MAX);
for (int c = 0; c < C; c++) {
for (int c2 = 0; c2 < C; c2++) {
dp[c2] = min(dp[c2], pre[c] + moveCost[grid[r][c]][c2] + grid[r + 1][c2]);
}
}
pre.swap(dp);
}
return *min_element(pre.begin(), pre.end());
}
};
单元测试
vector<vector<int>> grid, moveCost;
TEST_METHOD(TestMethod11)
{
grid = { {5,3},{4,0},{2,1} }, moveCost = { {9,8},{1,5},{10,12},{18,6},{2,4},{14,3} };
auto res = Solution().minPathCost(grid, moveCost);
AssertEx(17, res);
}
TEST_METHOD(TestMethod12)
{
grid = { {5,1,2},{4,0,3} }, moveCost = { {12,10,15},{20,23,8},{21,7,1},{8,1,13},{9,10,25},{5,3,2} };
auto res = Solution().minPathCost(grid, moveCost);
AssertEx(6, res);
}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
原文地址：https://blog.csdn.net/he_zhidan/article/details/143326663
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！