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

题目来自力扣.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