剑指 Offer 47. 礼物的最大价值

class Solution {
    
    public int maxValue(int[][] grid) {
    
        int n = grid[0].length, m = grid.length; 
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];

        for(int i = 1; i < n ; i++){
    
            dp[0][i] += dp[0][i-1] + grid[0][i];
        }
        for(int i = 1; i < m ; i++){
    
            dp[i][0] += dp[i-1][0] + grid[i][0];
        }
        for(int i = 1; i < m; i++){
     // 从第二行开始
            for(int j = 1; j < n; j++){
     // 从第二列开始 
                dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

class Solution {
    
    public int maxValue(int[][] grid) {
    
        int n = grid[0].length, m = grid.length; // 列数
        int[] arr = grid[0]; // 第一行前缀和
        for(int i = 1; i < n ; i++){
    
            arr[i] += arr[i-1];
        }
        for(int i = 1; i < m; i++){
     // 从第二行开始
            arr[0] += grid[i][0];
            for(int j = 1; j < n; j++){
     // 从第二列开始
                // arr[j] = Math.max(arr[j], arr[j-1]) + grid[i][j];
                arr[j] = (arr[j] > arr[j-1] ? arr[j] : arr[j-1]) + grid[i][j];
            }
        }
        return arr[n-1];
    }
}