在一个的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 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
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]; } }
//二维动态规划,创建一个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]; } }
class Solution: def maxValue(self , grid: List[List[int]]) -> int: m = len(grid) n = len(grid[0]) dp = [[0 for _ in range(n)] for _ in range(m)] dp[0][0] = grid[0][0] for i in range(1, m): dp[i][0] = dp[i - 1][0] + grid[i][0] for i in range(1, n): dp[0][i] = dp[0][i - 1] + grid[0][i] for i in range(1, m): for j in range(1, n): if i < m and j < n: dp[i][j] = max(dp[i][j - 1] + grid[i][j], dp[i - 1][j] + grid[i][j]) return dp[m - 1][n - 1]
function maxValue(grid) { // write code here let n = grid.length; let m = grid[0].length; let dp = []; for (let i = 0; i < n; i++) { dp[i] = []; } for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if (j === 0 && i === 0) { dp[i][j] = grid[0][0]; } else if (i === 0) { dp[i][j] = dp[i][j - 1] + grid[i][j]; } else if (j === 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[n - 1][m - 1]; }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param grid int整型vector<vector<>> * @return int整型 */ int maxValue(vector<vector<int> >& grid) { // 时间复杂度O(N^2),空间复杂度O(N^2) int dp[grid.size()][grid[0].size()]; dp[0][0] = grid[0][0]; for (int i = 1; i < grid.size(); ++i) dp[i][0] = dp[i - 1][0] + grid[i][0]; for (int j = 1; j < grid[0].size(); ++j) dp[0][j] = dp[0][j - 1] + grid[0][j]; for (int i = 1; i < grid.size(); ++i) { for (int j = 1; j < grid[0].size(); ++j) { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[grid.size() - 1][grid[0].size() - 1]; } };
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]; }
int maxValue(int** grid, int gridRowLen, int* gridColLen ) { // write code here int m=gridRowLen; int n=*gridColLen; //对新数组的第一行重新赋值,第一行的最大值只能来自最左边,第一个值是固定不变的 for (int j=1; j<n; j++) { grid[0][j]+=grid[0][j-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]= grid[i][j-1]>grid[i-1][j]?grid[i][j]+grid[i][j-1]:grid[i][j]+grid[i-1][j]; } } return grid[m-1][n-1]; }
int maxValue(int** grid, int gridRowLen, int* gridColLen) { // 判断输入是否合法 if (grid == NULL || gridRowLen <= 0 || gridColLen == NULL || *gridColLen <= 0) { return 0; } int m = gridRowLen; int n = *gridColLen; // 创建 dp 数组并初始化第一个格子 int dp[m][n]; dp[0][0] = grid[0][0]; // 初始化第一行 for (int j = 1; j < n; j++) { dp[0][j] = dp[0][j-1] + grid[0][j]; } // 初始化第一列 for (int i = 1; i < m; i++) { dp[i][0] = dp[i-1][0] + grid[i][0]; } // 计算其他格子的最大价值 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = fmax(dp[i-1][j], dp[i][j-1]) + grid[i][j]; } } // 返回右下角格子的最大价值 return dp[m-1][n-1]; } //x++||y++
class Solution: def maxValue(self , grid: List[List[int]]) -> int: # write code here # 动态规划 m, n = len(grid), len(grid[0]) # dp[i][j]表示到达(i, j)位置时的最大价值 dp = [[0] * n for _ in range(m)] # 初始化第一行和第一列 dp[0][0] = grid[0][0] for i in range(1, m): dp[i][0] = dp[i - 1][0] + grid[i][0] for j in range(1, n): dp[0][j] = dp[0][j - 1] + grid[0][j] for i in range(1, m): for j in range(1, n): dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] return dp[-1][-1]
int max_val(int a,int b) { return a>b?a:b; } int maxValue(int** grid, int gridRowLen, int* gridColLen ) { // write code here int i=0,col = *gridColLen; for(i=gridRowLen-2;i>=0;i--) grid[i][col-1] += grid[i+1][col-1]; for(i=col-2;i>=0;i--) grid[gridRowLen-1][i] += grid[gridRowLen-1][i+1]; for(int i=gridRowLen-2;i>=0;i--) for(int j=col-2;j>=0;j--) grid[i][j] +=max_val(grid[i+1][j],grid[i][j+1]); return grid[0][0]; }
import java.util.*; //二维动态规划,创建一个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]) public class Solution { /** * @param grid int整型二维数组 * @return int整型 */ public int maxValue (int[][] grid) { // write code here 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[dp.length - 1][dp[0].length - 1]; } }
package main import _"fmt" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param grid int整型二维数组 * @return int整型 */ func maxValue( grid [][]int ) int { m,n:=len(grid),len(grid[0]) for i:=1;i<m;i++{ grid[i][0]+=grid[i-1][0] } for i:=1;i<n;i++{ grid[0][i]+=grid[0][i-1] } for i:=1;i<m;i++{ for j:=1;j<n;j++{ grid[i][j]+=max(grid[i-1][j],grid[i][j-1]) } } return grid[m-1][n-1] } func max(a,b int)int{ if a>b{ return a } return b }
class Solution: def maxValue(self , grid: List[List[int]]) -> int: # write code here # 动态规划 m, n = len(grid), len(grid[0]) dp = [[0 for j in range(n + 1)] for i in range(m + 1)] for i in range(1, m + 1): for j in range(1,n + 1): dp[i][j] = max(grid[i - 1][j - 1] + dp[i - 1][j], grid[i - 1][j - 1] + dp[i][j - 1]) return dp[-1][-1] 动态规划,每次走最大路径即可完成
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param grid int整型二维数组 # @return int整型 # class Solution: def maxValue(self, grid: List[List[int]]) -> int: # write code here M = len(grid) N = len(grid[0]) dp = [[0]*N for m in range(M)] # 记录当前位置的礼物的最大 for i in range(0, len(grid)): for j in range(0, len(grid[0])): # 初始化第一行,第一列的元素,它不可能从上面,或者左边移动过来,所以说它的大小就是它最大的价值 if i == 0 and j == 0: print(grid[0][0]) dp[i][j] = grid[i][j] # 棋盘中非第一行,非第一列中的元素的最大的情况 elif len(grid) > i > 0 and len(grid[0]) > j > 0: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] # 棋盘的第一行只能从左移动过去,从上面移动下来不可能 elif i-1 < 0: print("行列", i, j) dp[i][j] = dp[i][j-1]+grid[i][j] # 棋盘的第一列,不可能从左边移动过来,所以只能从上面移动过来 elif j-1 < 0: dp[i][j] = dp[i-1][j] + grid[i][j] return dp[M-1][N-1]
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param grid int整型vector<vector<>> * @return int整型 */ int maxValue(vector<vector<int> >& grid) { // write code here int m=grid.size(); //行数m int n=grid[0].size(); //列数n int rec[m][n]; //记录最大值的二维数组rec,这里空间复杂度高一些 rec[0][0]=grid[0][0]; //初始化左上角rec for(int i=1;i<m;i++){ //填补rec的第一列 rec[i][0]=rec[i-1][0]+grid[i][0]; } for(int i=1;i<n;i++){ //填补rec的第一行 rec[0][i]=rec[0][i-1]+grid[0][i]; } for(int i=1;i<m;i++){ //找剩下的rec空的地方的最大值,遍历一遍 for(int j=1;j<n;j++){ rec[i][j]=max(rec[i-1][j],rec[i][j-1])+grid[i][j]; } } return rec[m-1][n-1]; } };
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param grid int整型vector<vector<>> * @return int整型 */ int maxValue(vector<vector<int> >& grid) { // write code here vector<vector<int>>dp(grid.size(),vector<int>(grid[0].size()));//dp[i][j]表示在位置grid[i][j]时的最大价值 //初始化 dp[0][0]=grid[0][0]; for(int i=1;i<grid.size();i++)dp[i][0]=dp[i-1][0]+grid[i][0]; for(int i=1;i<grid[0].size();i++)dp[0][i]=dp[0][i-1]+grid[0][i]; for(int i=1;i<grid.size();i++) for(int j=1;j<grid[0].size();j++){ dp[i][j]=max(dp[i][j-1]+grid[i][j],dp[i-1][j]+grid[i][j]); } return dp[grid.size()-1][grid[0].size()-1]; } };
//定义二维数组 class Solution { public: int maxValue(vector<vector<int> >& grid) { // write code here int m = grid.size(); int n = grid[0].size(); vector<vector<int>> dp(m, vector<int>(n, 0)); dp[0][0] = grid[0][0]; for (int i = 1; i < m; i++) { dp[i][0] = grid[i][0] + dp[i - 1][0]; } for (int j = 1; j < n; j++) { dp[0][j] = grid[0][j] + dp[0][j - 1]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = max(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]); //cout << dp[i][j] << endl; } } return dp[m - 1][n - 1]; } };