为什么我在Matrix中填Integer.MAX_VALUE

Question

本题出自LeetCode 174.地下城游戏

代码能够运行正确。

但是如果我删除 for (int[] level : dp) Arrays.fill(level, Integer.MAX_VALUE); ，代码将失败。

为什么代码不能运行，如果我删除for (int[] level : dp) Arrays.fill(level, Integer.MAX_VALUE);

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {    
        int rows = dungeon.length;
        int cols = dungeon[0].length;
        int[][] dp = new int[rows + 1][cols + 1];

         for (int[] level : dp) Arrays.fill(level, Integer.MAX_VALUE);


        dp[rows][cols - 1] = 1;  
        dp[rows - 1][cols] = 1;

        for(int i = rows - 1; i >= 0; i--){
            for(int j = cols - 1; j >= 0; j--){
                int min = Math.min(dp[i][j + 1] , dp[i + 1][j]) - dungeon[i][j];
                dp[i][j] = min <= 0 ? 1 : min; 
            }
        }

        return dp[0][0]; 
    }
}

Answer 1

使用Integer.MAX_VALUE的原因与以下行有关：

int min = Math.min(dp[i][j + 1] , dp[i + 1][j]) - dungeon[i][j];

在不知道您的代码的完整逻辑的情况下，很明显，对 Math.min() 的调用试图找到两个点中较小的一个。假设您只将实际游戏数据分配给一个点，那么分配的任何单个值都将显示为最小值。这也假设您永远不会拥有像 Integer.MAX_VALUE.

这样大的游戏数据

Answer 2

因为min(Integer.MAX_VALUE, anything_else) = anything_else.

因此，在数组中查找最小值的代码应该从 min=MAX_VALUE 开始，假设必须有一个值小于数组中某处的值。

found_min=MAX_VALUE
for (int i=0 ; i<size ; ++i)
  found_min = min(arr[i], found_min)

此代码失败的唯一方法是当数组为空时，然后返回的 found_min 将保持 MAX_VALUE。

为什么我在Matrix中填Integer.MAX_VALUE

Why do I fill Integer.MAX_VALUE in Matrix

java

arrays

2d

dynamic

integer-overflow