龙与地下城游戏问题

import java.util.*;
public class Solution {
    //经典的动态规划问题，定义和地图大小一样的矩阵，记为dp,dp[i][j]的含义是如果骑士要走上位置(i,j)
    //并且从该位置选一条最优的路径，最后走到右下角，骑士起码应该具备的血量。最终我们需要的是dp[0][0]
    //如果骑士在当前位置加完血或者扣完血之后的血量只要等于dp[i][j+1]即可
    //那么骑士在加血或者扣血之前的血量要求，就是dp[i][j+1]-mp[i][j]。
    //同时要求骑士血量随时不少于1，所以向右的要求为max{dp[i][j+1]-map[i][j],1}，向下走也是同样的分析
    //因为骑士要走最优的一条，所以，dp[i][j]=min{向右的要求，向下的要求}
    public int dnd (ArrayList<ArrayList<Integer>> mp) {
       if(mp==null||mp.size()==0||mp.get(0)==null||mp.get(0).size()==0) return 1;
        int row=mp.size();
        int col=mp.get(0).size();
        int[][] dp=new int[row--][col--];
        dp[row][col]=mp.get(row).get(col)>0?1:-mp.get(row).get(col)+1;
        for(int j=col-1;j>=0;j--){
            dp[row][j]=Math.max(dp[row][j+1]-mp.get(row).get(j),1); 
        }
        int right=0;
        int down=0;
        for(int i=row-1;i>=0;i--){
            dp[i][col]=Math.max(dp[i+1][col]-mp.get(i).get(col),1);
            for(int j=col-1;j>=0;j--){
                right=Math.max(dp[i][j+1]-mp.get(i).get(j),1); //向右的要求
                down=Math.max(dp[i+1][j]-mp.get(i).get(j),1); //向下的要求
                dp[i][j]=Math.min(right,down);  //dp[i][j]=min{right,down}
            }
        }
        return dp[0][0];
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param mp int整型vector<vector<>> 
     * @return int整型
     */
    int dnd(vector<vector<int> >& mp) {
        // write code here
        int m = mp.size() , n = mp[0].size();
        vector<vector<int>> dp(m,vector<int>(n,1));
        dp[m-1][n-1] = 1;
        for(int j = n - 2; j >= 0;j--){
            dp[m-1][j] = max(dp[m - 1][j + 1] - mp[m - 1][j + 1],1);
        }
        for(int i = m - 2;i >= 0;i--){
            dp[i][n-1] = max(dp[i + 1][n-1] - mp[i + 1][n - 1],1);
        }
        for(int i = m - 2;i >= 0;i--){
            for(int j = n - 2;j >= 0;j--){
                dp[i][j] = min(max(dp[i + 1][j] - mp[i + 1][j],1),max(dp[i][j + 1] - mp[i][j + 1],1));
            }
        }
        return max(dp[0][0] - mp[0][0],1);
    }
};