自己做出来了!奥利给!
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];
}
}