【动态规划】【 矩阵】【逆向思考】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 ，所以非终点格条件二可以省略。

代码

核心代码

class Solution {
public:
	int calculateMinimumHP(vector<vector>& dungeon) {
		m_r = dungeon.size();
		m_c = dungeon.front().size();
		vector<vector> dp(m_r, vector(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
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& 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> 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& dungeon) {

m_r = dungeon.size();

m_c = dungeon[0].size();

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++**实现。