首页 > 代码库 > 地下城游戏

地下城游戏

题目:给一个n*m的格子,每个格子里有一些值,负的代表要减去,正的代表可以加上,从左上到右下,走到每个格子时,值不能小于等于0,求最小的初始值

思路:从右下到左上求到达每个格子的最小值

  public int calculateMinimumHP(int[][] dungeon) {
        int n=dungeon.length,m=dungeon[0].length;
        if(n==0||m==0) return 0;
        int[][] dp = new int[n][m];
        dp[n-1][m-1]=Math.max(1-dungeon[n-1][m-1],1);
        for(int i=n-2;i>=0;i--){
            dp[i][m-1]=Math.max(dp[i+1][m-1]-dungeon[i][m-1],1);
           
            
        }
        for(int i=m-2;i>=0;i--){
            dp[n-1][i]=Math.max(dp[n-1][i+1]-dungeon[n-1][i],1);
         
        }
        for(int i=n-2;i>=0;i--){
            for(int j=m-2;j>=0;j--){
                dp[i][j]=Math.min(Math.max(dp[i+1][j]-dungeon[i][j],1),Math.max(dp[i][j+1]-dungeon[i][j],1));
            }
        }
         return dp[0][0];
    }

 

地下城游戏