leetcode 174. 地下城游戏「动态规划」「逆向思维」

174. 地下城游戏

题目描述：

二维矩阵，每个点都有一个价值，起点是左上角(1, 1)，终点是右下角(n, m)，初始价值为一个未知的正整数，每次只能往下或者往右走一步，到达一个新的点都要加上这个点的价值，过程中要保证总价值每时每刻的都要大于0(包括初始值)，求所需的最小初始价值

思路：

一眼dp

这个题很显然可以转换成找一条路径，将路径上的价值看成一个数组，做前缀和，求前缀和数组的最小值 $minx$，答案就是$max(1,1-minx)$

可以发现，我们需要在遍历的过程中维护两个变量，一个是从出发点到当前点的路径和，另一个是从出发点到当前点的所需的最小初始值

我们希望 从出发点到当前点的路径和 尽可能大，而 从出发点到当前点所需的最小初始值 尽可能小。这样转移方式也有两种，选择1会对后面的2好，选择2会对后面的1好，这两种转移方式各有优劣，其重要程度是相当的，会同时影响状态转移，这样的动态规划是不满足无后效性的

所以我们逆向考虑，考虑另一种状态：从 $(i,j)$到 $(n,m)$所需要的最小初始值，此时我们不需要考虑从$(1,1)$到 $(i,j)$的路径和，所以状态转移方式是：

$dp[i][j]=max(min(dp[i-1][j],dp[i][j-1])-ar[i][j],1)$

这个时候我们从右下角往左上角遍历，然后处理好边界就行

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int n = dungeon.size(), m = dungeon[0].size();
        vector<vector<int>>dp(n + 1, vector<int>(m + 1, 1e9));
        for(int i = n - 1; i >= 0; --i){
            for(int j = m - 1; j >= 0; --j){
                if(i == n - 1 && j == m - 1)dp[i][j] = max(1, -dungeon[i][j]+1);
                else dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
};