题解 | 礼物的最大价值

import java.util.*;


public class Solution {
    public int maxValue (int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        // 处理只有一行或者一列的情况
        if(grid.length == 1){
            int res = 0;
            for(int i = 0;i<grid[0].length;i++){
                res += grid[0][i];
            }
            return res;
        }
        if(grid[0].length == 1){
            int res = 0;
            for(int i = 0;i<grid.length;i++){
                res += grid[i][0];
            }
            return res;
        }
        // 初始化dp数组，将第一行和第一列的值初始化
        dp[0][0] = grid[0][0];
        for(int i = 1;i<grid.length;i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int j = 1;j<grid[0].length;j++){
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        // 除第一行和第一列外，dp[i][j] = Math.max(dp[i-1][j],dp[i][j - 1]) + grid[i][j];
        // 计算出所有的值
        for(int i = 1;i<grid.length;i++){
            for(int j = 1;j<grid[0].length;j++){
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j - 1]) + grid[i][j];
            }
        }
        // 最后返回右下角出口的结果
        return dp[grid.length-1][grid[0].length-1];
    }
}