地下城游戏（dp）

题目：https://leetcode-cn.com/problems/dungeon-game/ 题意：给定一个矩阵，从（0，0）走到(n-1,m-1)，每次只能向下和向右走，要求在过程中血量必须保持正值。求最低初始血量。 题解：这是最小值最大化问题。正向不好递推，考虑逆向。令 d p [ i ] [ j ] dp[i][j] dp[i][j]表示走到该点时需要的最小血量。如果其相邻点都为负数，代表往后走需要额外消耗，取最小消耗，加上自己的点值；如果相邻点存在正值，说明往后走不需要额外消耗，只需考虑自己的点值即可。

class Solution {
public:
    int calculateMinimumHP(vector& dungeon) {
        int n = dungeon.size();
        if(!n) return 0;
        int m = dungeon[0].size();
        if(!m) return 0;
        vectordp = vector(n+1,vector(m+1));
        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] = dungeon[i][j];
                    continue;
                }
                dp[i][j] = INT_MIN;
                if(i  0) return 1;
        return -dp[0][0]+1;
    }
};