【动态规划】【矩阵】【逆向思考】C++算法174地下城游戏

作者推荐

【动态规划】【字符串】扰乱字符串

本文涉及的基础知识点

动态规划矩阵逆向思考

LeetCode174地下城游戏

恶魔们抓住了公主并将她关在了地下城 dungeon 的右下角。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快解救公主，骑士决定每次只向右或向下移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
示例 1：
输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出：7
解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7 。
示例 2：
输入：dungeon = [[0]]
输出：1
参数：
m == dungeon.length
n == dungeon[i].length
1 <= m, n <= 200
-1000 <= dungeon[i][j] <= 1000

正向思考

每个单格需要记录如下信息：a，从起点到当前点增加（消耗）的健康。b，整个路径的最小健康（最大消耗）。
两种信息的最大可能2^m+n ，其实信息b 只有n+m种可能，我们记录最小健康所在单格。r,c,b 确定的情况下：a越大越好。
这样有nmnm种状态。空间复杂度是:O(nnmm)
每种状态的转移时间复杂度是O(nm)。
总时间复杂度O(nnnmmm)，铁定超时

逆向动态规范

能够进入dungeon[r][c]的两个条件：
一，dp[r][c] >=1
二，dp[r][c] + dungeon[r][c]>=1 ===>>>> dp[r][c] >= 1 = dungeon[r][c]
非终点格还需要符合三或符合四。
三，dp[r][c] + dungeon[r][c] >= dp[r+1][c]
四，dp[r][c] + dungeon[r][c] >= dp[r][c+1]
由于dp[r+1][c]和dp[r][c+1]必定>=1 ，所以非终点格条件二可以省略。


动态规划的状态表示	dp[r][c]表示进入当前单格需要的最小健康度
动态规划的转移方程	能进入当前单格，能进入右边或下边的格子
动态规划的初始状态	dp[r-1][c-1]=max(1,1-dungeon [r-1][c-1]
动态规划的填表顺序	r c都从大到小处理,确保动态规划的无后效性
动态规划的返回值	dp[0][0]

代码

核心代码

class Solution {
public:
	int calculateMinimumHP(vector<vector<int>>& dungeon) {
		m_r = dungeon.size();
		m_c = dungeon.front().size();
		vector<vector<int>> dp(m_r, vector<int>(m_c, INT_MAX));
		dp.back().back() = max(1, 1 - dungeon.back().back());
		for (int r = m_r - 1; r >= 0; r--)
		{
			for (int c = m_c - 1; c >= 0; c--)
			{
				if (r+1 < m_r)
				{		
					dp[r][c] = min(dp[r][c], dp[r + 1][c] - dungeon[r][c]);
				}
				if (c+1 < m_c)
				{
					dp[r][c] = min(dp[r][c], dp[r][c+1] - dungeon[r][c]);
				}
				dp[r][c] = max(1, dp[r][c]);
			}
		}
		return dp[0][0];
	}
	int m_r, m_c;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}


int main()
{
	vector<vector<int>> dungeon;
	{
		Solution sln;
		dungeon = { {0} };
		auto res = sln.calculateMinimumHP(dungeon);
		Assert(1, res);
	}
	{
		Solution sln;
		dungeon = { {-2,-3,3},{-5,-10,1} };
		auto res = sln.calculateMinimumHP(dungeon);
		Assert(6, res);
	}
	{
		Solution sln;
		dungeon = { {-2,-3,3},{-5,-10,1},{10,30,-5} };
		auto res = sln.calculateMinimumHP(dungeon);
		Assert(7, res);
	}
	
}

2023年1月版

class Solution {
public:
int calculateMinimumHP(vector<vector>& dungeon) {
m_r = dungeon.size();
m_c = dungeon[0].size();
vector<vector> dp;
dp.assign(m_r, vector(m_c, INT_MAX));
//不考虑候选，进入本格的最小值
for (int r = m_r - 1; r >= 0; r–)
{
for (int c = m_c - 1; c >= 0; c–)
{
dp[r][c] = (dungeon[r][c] > 0) ? 1 : (1 - dungeon[r][c]);
}
}
for (int r = m_r - 1; r >= 0; r–)
{
for (int c = m_c - 1; c >= 0; c–)
{
int tmp = INT_MAX;
if (c + 1 < m_c)
{//可以右移
tmp = min(tmp,dp[r][c + 1] - dungeon[r][c]);
}
if (r + 1 < m_r)
{
tmp = min(tmp, dp[r + 1][c] - dungeon[r][c]);
}
if (INT_MAX == tmp)
{
continue;
}
dp[r][c] = max(dp[r][c], tmp);
}
}
/*
if (r > 0)
{
dp[r - 1][c] = min(dp[r - 1][c],)
}*/
return dp[0][0];
}
int m_r, m_c;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛