【C++动态规划】2304. 网格中的最小路径代价|1658

本文涉及知识点

C++动态规划

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);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功