在一个的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
如输入这样的一个二维数组,
[
[1,3,1],
[1,5,1],
[4,2,1]
]
[
[1,3,1],
[1,5,1],
[4,2,1]
]
那么路径 1→3→5→2→1 可以拿到最多价值的礼物,价值为12
[[1,3,1],[1,5,1],[4,2,1]]
12
public int maxValue (int[][] grid) { // write code here int row = grid.length, col = grid[0].length; for(int i = 1; i < grid.length; ++i) { grid[i][0] += grid[i-1][0]; } for(int j = 1; j < col; ++j) { grid[0][j] += grid[0][j-1]; } for(int i = 1; i < row; ++i){ for(int j = 1; j < col; ++j) { grid[i][j] += Math.max(grid[i-1][j], grid[i][j-1]); } } return grid[row-1][col-1]; }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param grid int整型二维数组 * @return int整型 */ private int dp(int[][] grid,int i,int j){ if(i==0&&j==0){ return grid[0][0]; } if(i==0){ return dp(grid,i,j-1)+grid[i][j]; } if(j==0){ return dp(grid,i-1,j)+grid[i][j]; } return Math.max(dp(grid,i-1,j),dp(grid,i,j-1))+grid[i][j]; } public int maxValue (int[][] grid) { // write code here return dp(grid,grid.length-1,grid[0].length-1); } }
public int maxValue (int[][] grid) { // write code here int m = grid.length; int n = grid[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 && j == 0) continue; if (i == 0) grid[i][j] += grid[i][j - 1] ; else if (j == 0) grid[i][j] += grid[i - 1][j]; else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]); } } return grid[m - 1][n - 1]; } }
/** * 礼物的最大价值 右下角点的最大价值为到达他所有可能路径的最大值 左边和上边 * 状态:数组的坐标 * 选择:怎么走 右还是下 * 状态转移方程: dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + grid[i][j] * base case: dp[0][0] = grid[0][0] * @param grid * @return */ public int maxValue (int[][] grid) { int[][] dp = new int[grid.length][grid[0].length]; // 自作向右自上而下 dp[0][0] = grid[0][0]; for(int i = 0; i < grid.length; i++){ for(int j = 0; j < grid[0].length; j++){ if(i == 0 && j == 0) dp[i][j] = dp[0][0]; else if(i - 1 < 0) dp[i][j] = dp[i][j - 1] + grid[i][j]; else if(j - 1 < 0) dp[i][j] = dp[i - 1][j] + grid[i][j]; else 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]; }
public class Solution { public int maxValue (int[][] grid) { int row = grid.length, column = grid[0].length; int[][] dp = new int[row][column]; dp[0][0] = grid[0][0]; //初始化第一行和第一列(dp方程里有i-1和j-1,边界到第一行和第一列) for(int j = 1; j < column; 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]; for(int i = 1; i < row; i++){ for(int j = 1; j < column; j++){ dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j]; } } return dp[row-1][column-1]; } }
public int maxValue (int[][] grid) { /** * @param grid * @return int * @description 二维数组中左上角->右下角, * @direction 右,下 * @target maxValue * @state transition equation: dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + grid[i][j] */ int m = grid.length,n = grid[0].length; int[][] dp = new int[m][n]; dp[0][0] = grid[0][0]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(i==0 && j==0){ dp[i][j] = grid[0][0]; }else if(i==0 && j!=0){ dp[i][j] = dp[0][j-1] + grid[0][j]; }else if(i!=0 && j==0){ dp[i][j] = dp[i][j-1]; }else{ dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + grid[i][j]; } } } return dp[m-1][n-1]; }
我这个哪里有问题啊,为啥没全部通过啊
import java.util.*; public class Solution { public int maxValue (int[][] grid) { int m = grid.length; int n = grid[0].length; // 上边界赋值 for (int i = 1; i < n; i++) { grid[0][i] = grid[0][i] + grid[0][i - 1]; } // 左边界赋值 for (int i = 1; i < m; i++) { grid[i][0] += grid[i - 1][0]; } // 其余 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { // 取左、上较大值 grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]); } } return grid[m - 1][n - 1]; } }
public class Solution { public int maxValue (int[][] grid) { int[][] dp = new int[grid.length][grid[0].length]; for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ int fromLeft = j-1>=0?dp[i][j-1]:0; int fromOver = i-1>=0?dp[i-1][j]:0; dp[i][j] = grid[i][j] + Math.max(fromLeft,fromOver); } } return dp[grid.length-1][grid[0].length-1]; } }
//二维动态规划,创建一个dp二维数组,长度比grid大一 //dp中存放对应的grid数组中走到这个位置的礼物最大价值, //状态转移方程: //dp[i][j] = Math.max( dp[i-1][j] + grid[i-1][j-1], dp[i][j-1] + grid[i-1][j-1]) import java.util.*; public class Solution { public int maxValue (int[][] grid) { int[][] dp = new int[grid.length+1][grid[0].length+1]; for(int i = 1; i < dp.length ; i++){ for(int j = 1 ; j < dp[0].length ; j++){ dp[i][j] = Math.max(dp[i-1][j]+grid[i-1][j-1],dp[i][j-1]+grid[i-1][j-1]); } } return dp[grid.length][grid[0].length]; } }
public int maxValue (int[][] grid) { // write code here int row = grid.length; int col = grid[0].length; for (int i = col - 2; i >= 0; i --) { grid[row - 1][i] += grid[row - 1][i + 1]; } for (int i = row - 2; i >= 0; i --) { grid[i][col - 1] += grid[i + 1][col - 1]; } for (int i = row - 2; i >= 0; i --) { for (int j = col - 2; j >= 0; j--) { grid[i][j] += Math.max(grid[i + 1][j], grid[i][j + 1]); } } return grid[0][0]; }
public int maxValue (int[][] grid) { int maxRow = grid.length; int maxCol = grid[0].length; // 创建递推矩阵: for(int i=0;i<maxRow;i++){ for(int j=0;j<maxCol;j++){ // 排除原点 if(i==0 && j==0){ continue; } // 对于上边界和左边界上的值,当前值 = 当前值+之前所有值的和 else if(i==0){ grid[i][j] += grid[i][j-1]; }else if(j==0){ grid[i][j] += grid[i-1][j]; } // 对于其他位置的值,当前值 = 当前值+max(上边值,左边值) else { grid[i][j] += Math.max(grid[i][j-1],grid[i-1][j]); } } } return grid[maxRow-1][maxCol-1]; }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param grid int整型二维数组 * @return int整型 */ public int maxValue (int[][] grid) { // write code here for(int i = 0; i < grid.length; i++){ for(int j = 0; j < grid[0].length; j++){ if(i == 0 && j == 0) continue; if(i == 0) grid[i][j] += grid[i][j - 1]; // 上边界,只能从左边来 else if(j == 0) grid[i][j] += grid[i -1][j]; // 左边界,只能从上边来 else grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]); // 其他情况选择从上和从左来中更大的那个 } } return grid[grid.length - 1][grid[0].length - 1]; } }