题解 | #礼物的最大价值#

自己做出来了！奥利给！

import java.util.*;

public class Solution {

//递归解法  超时了
public int getMax(int[][] grid, int i, int j,int row,int col){
    //亚瑟走到终点了
    if(i==row-1 && j==col-1)
        return grid[i][j];
    int right_max=0,down_max=0;
    if(j!=col-1)
    //亚瑟走右路
        right_max = grid[i][j] + getMax(grid,i,j+1,row,col);
    //亚瑟不走右路，走下路
    if(i!=row-1)
        down_max = grid[i][j] + getMax(grid,i+1,j,row,col);
    return Math.max(right_max,down_max);
}

public int maxValue (int[][] grid) {
    // write code here
    // return getMax(grid,0,0,grid.length,grid[0].length);

    int row = grid.length, col=grid[0].length;
    int[][] dp = new int[row][col];
    dp[0][0] = grid[0][0];
    //第一行初始化  亚瑟先一路向东
    for(int j=1;j<col;++j)
        dp[0][j] = dp[0][j-1]+grid[0][j];
    //第一列初始化  亚瑟一路向南
    for(int i=1;i<row;++i)
        dp[i][0] = dp[i-1][0] + grid[i][0];
    //接着亚瑟一路过五关斩六将，逐步填充剩下的dp元素的值，直到最后一个，这里按行填充
    //因为规定只能往右走或往下走  所以寻找的话是寻找是上面元素和左边元素的最大值
    for(int i=1;i<row;++i){
        for(int j=1;j<col;++j){
            dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j];
        }
    }
    return dp[row-1][col-1];
}

}