Topic describes

// The maximum value of a gift // the maximum value of a gift // the maximum value of a gift // The maximum value of a gift // The maximum value of a gift // The maximum value of a gift // The maximum value of a gift // You can start at the top left corner of the board and move to the right or down one space at a time until you reach the bottom right corner. Given a chess board and the value of the gifts on it, calculate what is the most valuable gift you can get?Copy the code

Answer key

// The solution to the problem is not difficult. It is a dynamic programming, weighing which direction (left or top) the cumulative value is the greatest. // The cumulative value of which direction is the greatest. // We only need the maximum value from the top left to the bottom right. // Therefore, the same dynamic programming can be optimized according to the different storage methods of dynamic programming.Copy the code
// Local dp // execution time: 3 ms, beating 80.03% of all Java commits // Memory consumption: 41.1 MB, Beat the 58.97% of the users in all submitted Java class Solution {public int maxValue (int [] [] the grid) {if (grid = = null | | grid. The length = = 0) return 0; int row = grid.length, col = grid[0].length; for (int i = 0; i < row; i++) { for (int j = 0; j < col; 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[row - 1][col - 1]; }}Copy the code

Schematic diagram:

Then finally:

// Execution time: 2 ms, beating 97.66% of users in all Java commits // Memory consumption: 41.1 MB, Beat the 58.97% of the users in all submitted Java class Solution {public int maxValue (int [] [] the grid) {if (grid = = null | | grid [0]. Length = = 0) return 0; int col = grid[0].length; int[] dp = new int[col]; for (int[] row : grid) { dp[0] += row[0]; for (int i = 1; i < col; I ++) {// if dp[I] is not assigned, then dp[I - 1] is assigned to Math. dp[i] = Math.max(dp[i], dp[i - 1]) + row[i]; } } return dp[col - 1]; }}Copy the code

Schematic diagram: