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

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        vector<vector<int>> arr(a,vector<int>(b));
        vector<vector<int>> dp(a+1,vector<int>(b+1,0x3f3f3f3f));
        dp[a][b-1]=1;
        dp[a-1][b]=1;
        for(int i=0;i<a;i++)
            for(int j=0;j<b;j++)
                cin>>arr[i][j]; 
        //正向考虑，很难考虑清楚有血瓶的情况给后面的影响。
	  	//状态定义：
	  	//反向考虑dp[i][j]:从[i,j]位置开始到终点所需的最少血量。
	  	//状态转移：
	  	//（1）[i,j]能够到达的只有两个位置向下走：[i+1,j]，向右走[i,j+1];
	  	//（2）我们需要保证从[i,j]到[i+1,j]血量>=1,那么至少需要的血量就是：dp[i+1][j]-arr[i][j];
	  	//（3）我们需要保证从[i,j]到[i,j+1]血量>=1,那么至少需要的血量就是：dp[i][j+1]-arr[i][j];
	  	//（4）上述两种结果要去较小的一个
	  	//如果arr[i][j]>=0，即某一个位置有血瓶，上述计算dp[i+1][j]-arr[i][j]或dp[i][j+1]-arr[i][j]可能是一个负数，这就不符合游戏规则，最少需要的血量也要是1.
	  	//所以最终结果要和1取max。
        for(int i=a-1;i>=0;i--)
        {
            for(int j=b-1;j>=0;j--)
            {
                dp[i][j]=min(dp[i][j+1],dp[i+1][j])-arr[i][j];
                dp[i][j]=max(1,dp[i][j]);
            }
        }
        cout<<dp[0][0]<<endl;
    }
}