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

发布时间:2024年01月07日

作者推荐

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

本文涉及的基础知识点

动态规划 矩阵 逆向思考

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,整个路径的最小健康(最大消耗)。
两种信息的最大可能2m+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

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

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

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

文章来源:https://blog.csdn.net/he_zhidan/article/details/135406333
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。