欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

逆向动态规划-地下城救公主

程序员文章站 2022-06-27 14:46:07
题目来自力扣.174,一道很经典的动态规划题目一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K)最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球...

题目来自力扣.174,一道很经典的动态规划题目

一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K)最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。

有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。

为了尽快到达公主,骑士决定每次只向右或向下移动一步。

逆向动态规划-地下城救公主

说明:

骑士的健康点数没有上限。

任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。

题解

这道题目很容易想到动态规划的办法,自左上到左下,类似于避开障碍物寻找最短路径的题目。但是这种做法计算的是总路径的最小值,而题目要求的是最少用多少体力可以到达。最少用多少体力取决与两个中间量,
1.总路径之和(每次算体力都要用到)
2.在这条路径上的动态最小体力

自左上到左下的动态规划只能考虑其中的一种因素(1) ,而逆向动态规划(自右下到左上),可以直接考虑(2),从而忽视了影响因素(1),不需要去计算总路程之和,所以这道题应用逆向动态规划的思想,即可解决。

代码:

class Solution {
public:
	int calculateMinimumHP(vector<vector<int>>& dungeon) {
		int n = dungeon.size();
		int m = dungeon[0].size();
		vector<vector<int>>dp(n, vector<int>(m, 0));
        if(dungeon[n-1][m-1]>0) dp[n-1][m-1]=1;
        else dp[n-1][m-1]=-dungeon[n-1][m-1]+1;

		for (int i = n-1; i >=0; i--) {
			//最后一竖排赋值
			if (i == n-1) { continue; }
            if(dp[i+1][m-1]-dungeon[i][m-1]<1)
            //如果这个格子所需的体力小于1(不需要体力即可走到终点) 那么设定这个格子的最小体力为1
            //否则需要多少体力就填写多少体力dp
			dp[i][m-1] =1;
            else dp[i][m-1]=dp[i+1][m-1]-dungeon[i][m-1]; 
		}
		for (int i = m-1; i >= 0; i--) {
			//最后一横排赋值
			if (i == m-1) continue;
			if(dp[n-1][i+1]-dungeon[n-1][i]<1)
                dp[n-1][i]=1;
            else dp[n-1][i]=dp[n-1][i+1]-dungeon[n-1][i]; 
		}
       for(int i=n-1-1;i>=0;i--){
           for(int j=m-1-1;j>=0;j--){
             
               dp[i][j]=max(min(dp[i+1][j],dp[i][j+1])-dungeon[i][j],1);
           }
       }


		// for (int i = 0; i < n; i++) {
        //     //打印输出dp
		// 	for (int j = 0; j < m; j++) {
		// 		cout << dp[i][j];
		// 	}
		// 	cout << endl;
		// }
   
		return dp[0][0];
	}
};

逆向动态规划-地下城救公主

本文地址:https://blog.csdn.net/weixin_44866921/article/details/107330123