牛客网：龙与地下城游戏

这题是走迷宫的升级版本吧。

我们反着从终点走到起点，设dp[i][j]代表从(i,j)走到终点的最少血量。mp表示迷宫里面的值。

我们要知道dp[i][j]和右边下边的mp，dp的关系。

思路如下：

我们希望一个点能血量少一点就尽量少一点，即也是到达终点的最小血量，由题目可知最小血量是1。接着对dp[i][j]引入dp[i+1][j]-mp[i][j]和dp[i][j+1]-mp[i][j]两个量。

概括说一下这两个表达式求的都是要完成接下来的路径的当前节点血量的最小值，如果为负说明只要当前血量是个正值都可以走完下面的路径，我们可以直接取1，如果为正说明我们还需要至少有多少的血量才能保证在走完当前点后还能走完接下来的路径。

如果当前的矩阵mp[i][j]是负的，说明是要掉血的，那么显然我们从上一个点来的时候就要求血要多一些，如果是从左边来的，用dp[i][j+1]-mp[i][j]就得到了从左边那个点出发至少需要的血量（这个左边是当前点），这个血量要和1取最大值，因为至少是1，而小于1只能说明我们的mp[i][j]足够大，可能是个加血的，而求出来的值如果比1大则说明mp[i][j]足够小，所以我们要取更大的值以保证过了当前点后，仍然有血量走完接下来的路径。

如果是向下走思路类似。

以下是具体操作流程：

我们从终点开始走，首先初始化终点dp[n-1][m-1]=max(1, 1-mp[n-1][m-1])

之后对每个点更新dp[i][j]=max(1, min(dp[i+1][j], dp[i][j+1])-mp[i][j])，显然，对于第一列，第一行需要特殊处理。这里的min是因为我们始终要求最小的血量，max是因为我们的血量至少要是1

代码如下所示：

#include<bits/stdc++.h>
using namespace std;
// 递归
int solve1(int i, int j, int n, int m, vector<vector<int>> &mp, vector<vector<int>> &dp){
    if(dp[i][j]!=-1){
        return dp[i][j];
    }
    if(i==n-1 && j==m-1){
        dp[i][j]=max(1,1-mp[i][j]);    
    }else if(i==n-1){
        dp[i][j]=max(1, solve1(i, j+1, n, m, mp, dp)-mp[i][j]);
    }else if(j==m-1){
        dp[i][j]=max(1, solve1(i+1, j, n, m, mp, dp)-mp[i][j]);
    }else{
        dp[i][j]=max(1, min(solve1(i, j+1, n, m, mp, dp), solve1(i+1, j, n, m, mp, dp))-mp[i][j]);
    }
    return dp[i][j];
}
//递推
int solve2(int n,int m,vector<vector<int>> &mp, vector<vector<int>> &dp){
    dp[n-1][m-1]=max(1, 1-mp[n-1][m-1]);
    for(int i=n-2;i>=0;--i){
        dp[i][m-1]=max(1, dp[i+1][m-1]-mp[i][m-1]);
    }
    for(int j=m-2;j>=0;--j){
        dp[n-1][j]=max(1, dp[n-1][j+1]-mp[n-1][j]);
    }
    for(int i=n-2;i>=0;--i){
        for(int j=m-2;j>=0;--j){
            dp[i][j]=max(1, min(dp[i+1][j], dp[i][j+1])-mp[i][j]);
        }
    }
    return dp[0][0];
}
//空间优化
int solve3(int n, int m, vector<vector<int>> &mp, vector<int> &dp){
    dp[m-1]=max(1, 1-mp[n-1][m-1]);
    for(int i=m-2;i>=0;--i){
        dp[i]=max(1, dp[i+1]-mp[n-1][i]);
    }
    for(int i=n-2;i>=0;--i){
        dp[m-1]=max(1, dp[m-1]-mp[i][m-1]);
        for(int j=m-2;j>=0;--j){
            dp[j]=max(1, min(dp[j+1],dp[j])-mp[i][j]);
        }
    }
    return dp[0];
}


int main(){
    int m,n;
    cin>>n>>m;
    vector<vector<int>> mp(n, vector<int>(m));
//     vector<vector<int>> dp(n, vector<int>(m, -1));
    vector<int> dp(m);
    int res=INT_MAX;
    for(int i=0;i<m;++i){
        for(int j=0;j<n;++j){
            cin>>mp[i][j];
        }
    }
//     res=solve1(0,0,n,m,mp,dp);
//     res=solve2(n, m, mp, dp);
    res=solve3(n, m, mp, dp);
    cout<<res<<endl;
    return 0;
}

这是牛客网的一个题解带给我的启发~