题目：龙与地下城游戏

        给定一个二维数组map，含义是一张地图，例如，如下矩阵：

        -2   -3    1

        -5  -10   1

         0    30  -5

         游戏的规则如下：

• 骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。
• 地图中每个位置的值代表骑士要遭遇的事情。如果是负数，说明此处有怪兽，要让骑士损失血量。如果是非负数，代表此处有血瓶，能让骑士回血。
• 骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。

--------------------------------------------------------------------------------------------------------------

说明：

      原文作者利用Java进行实现，本文使用C++实现，供大家参考

解答：

      经典的动态规划的方法，如果 map 大小为 MxN，时间复杂度O(MN)，额外空间复杂度为O(MN)

      反向思考，因为要在每个路径上的点满足要求，最终求起点的血量，从终点开始逐渐向左上角移动。

      定义和地图大小一样的矩阵，记为dp，dp[i][j] 的含义是表示如果骑士要走上位置(i, j)，并且从该位置选一条最优的路径，最后走到右下角，骑士应有的血量。最终求得的是 dp[0][0] 的结果。

     以题目为例，map[2][2] = -5 ，骑士走上此位置之前至少需要 6 (6 -5 = 1)滴血才能活，dp[2][2] = 6

     dp[i][j] 如何计算？

      1. 如果骑士向右选择，dp[i][j]_1  = max{ dp[i][j+1] - map[i][j] , 1}

      2. 如果骑士向下选择，dp[i][j]_2  = max{ dp[i+1][j] - map[i][j] , 1}

      3. dp[i][j] = min{ dp[i][j]_1, dp[i][j]_2}

------------------------------------------------------------------------------------------------------------

代码如下：

// 龙与地下城游戏<动态规划> <复杂度0(N^2)>
#include<bits/stdc++.h>
using namespace std;
int minHP1(vector<vector<int>> map1);

int main(){
    cout<<"输入地图的维度M,N: ";
    int M, N;
    int temp;
    cin>>M>>N;
    vector<vector<int>> map1;
    vector<int> v1;
    for(int i = 0; i < M; i++){
        map1.push_back(v1);
    }
    for(int i = 0; i < M; i++){
        for(int j = 0; j < N; j++){
            cin >> temp;
            map1[i].push_back(temp);
        }
    }

    int result = minHP1(map1);
    cout << "初始血量："<< result<<endl;
    return 0;
}

int minHP1(vector<vector<int>> map1){
    int row = map1.size()-1 ;
    int col = map1[0].size()-1 ;
    vector<vector<int>> dp(row+1, vector<int>(col+1, 0));

    dp[row][col] = map1[row][col] > 0 ? 1 : (-map1[row][col] + 1);
    for(int j = col - 1; j >= 0; j--){
        dp[row][j] = max(dp[row][j+1] - map1[row][j], 1);
    }
    int right =  0;
    int down = 0;
    for(int i = row - 1; i >= 0; i--){
        dp[i][col] = max(dp[i+1][col] - map1[i][col], 1);
        for(int j = col - 1; j >= 0; j--){
            right = max(dp[i][j+1] - map1[i][j], 1);
            down = max(dp[i+1][j] - map1[i][j], 1);
            dp[i][j] = min(right, down);
        }
    }
    return dp[0][0];
}

编译器：codeblocks

输入：

输出：