AcWing 60. 礼物的最大价值(java---入门dp)
原题链接
中等
作者:
CYHMMZDAN
,
2023-01-03 16:20:54
,
所有人可见
,
阅读 156
class Solution {
public int getMaxValue(int[][] grid) {
int[][] dp=new int[1500][1500];
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 i=1;i<grid[0].length;i++){
dp[0][i]=dp[0][i-1]+grid[0][i];
}
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];
}
}