#yyds干货盘点# 动态规划专题：龙与地下城游戏问题

1.简述：

描述

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

游戏的规则如下:1）骑士从左上角出发，每次只能向右或向下走，最后到达右下角见到公主。2）地图中每个位置的值代表骑士要遭遇的事情。如果是负数，说明此处有怪兽，要让骑士损失血量。如果是非负数，代表此处有血瓶，能让骑士回血。3）骑士从左上角到右下角的过程中，走到任何一个位置时，血量都不能少于1。为了保证骑土能见到公主，初始血量至少是多少?

根据map,输出初始血量。

输入描述：

第一行两个正整数n，m  ，接下来n行，每行m个整数，代表。

输出描述：

输出一个整数，表示答案。

示例1

输入：

3 3
-2 -3 3
-5 -10 1
0 30 -5

输出：

7

示例2

输入：

2 2
1 1
1 1

输出：

1

2.代码实现：

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int m=input.nextInt();
        int [][]map=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                map[i][j]=input.nextInt();
            }
        }
        int [][]dp=new int[n][m];
//         用hpMatrix表示骑士从任意一格到达终点所需要的最少血量
        dp[n-1][m-1]=(map[n-1][m-1]>0?1:-map[n-1][m-1]+1);
        for(int j=m-2;j>=0;j--){
            if(map[n-1][j]-dp[n-1][j+1]>=0){
                dp[n-1][j]=1;
            }
            else{
                dp[n-1][j]=dp[n-1][j+1]-map[n-1][j];
            }
        }
        for(int i=n-2;i>=0;i--){
            if(map[i][m-1]-dp[i+1][m-1]>=0){
                dp[i][m-1]=1;
            }
            else{
                dp[i][m-1]=dp[i+1][m-1]-map[i][m-1];
            }
        }
        for(int i=n-2;i>=0;i--){
            for(int j=m-2;j>=0;j--){
                int minNeed=Math.min(dp[i+1][j],dp[i][j+1]);   //两个方向最少需要的血
                if(map[i][j]-minNeed>=0){  //同样的思路，如果够用，那就只需要1点血进来，因为最少一点血
                    dp[i][j]=1;
                }
                else{
                    dp[i][j]=minNeed-map[i][j]; //如果不够用的话，就只能增加进来时候的血
                }
            }
        }
        System.out.println(dp[0][0]);
    }
}