题解 | #龙与地下城游戏问题#

#include <iostream>
using namespace std;

int main() {
    int a, b;
    int n,m;
    cin>>n>>m;
    int dp[n+2][m+2];
    for(int i=0;i<n+2;i++)//设置地图四周
    {
        dp[i][0]=-100000;
        dp[i][m+1]=-100000;
    }
    for(int i=0;i<m+2;i++)//设置地图四周
    {
        dp[0][i]=-100000;
        dp[n+1][i]=-100000;
    }
    dp[n+1][m]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>dp[i][j];
        }
    }
    for(int i=n;i>0;i--)
    {
        for(int j=m;j>0;j--)
        {
            if(dp[i][j]<0&&(dp[i+1][j]>0||dp[i][j+1]>0))
                ;
            else
                dp[i][j]=dp[i][j]+max(dp[i+1][j],dp[i][j+1]);
        }
    }
    if(dp[1][1]>0)
    cout<<1;
    else
    cout<<-1*dp[1][1]+1;
}
// 64 位输出请用 printf("%lld")

逆推

dp[i][j]为dp[i][j]走到dp[n][m]所需最少的血，让其每一步血量都大于零

如果dp[i][j]<0而 dp[i+1][j]或者dp[i][j+1]>0则让dp[i][j]不用变

否则 dp[i][j]=dp[i][j]+max(dp[i+1][j],dp[i][j+1]);