Topic describes

Their thinking

  • Dynamic programming
  • First, construct an all-zero dp with the same dimensions as the original array
  • The value of dp first constructs the first row and first column as the sum of the values to the right and down of the original array
  • Then fill in the remaining DP values using a for loop
  • Equation dp [I] [j] = grid [I] [j] + math.h Max (dp [1], [I] dp [I – 1) [j].)

The implementation code

var maxValue = function(grid) {
    // Create a matrix with the same dimensions as the grid matrix
    const dp = [];
    const rowNum = grid.length;
    const cowNum = grid[0].length;
    for (let i = 0; i < rowNum; i++) { dp[i] = [];for (let j = 0; j < cowNum; j++) { dp[i][j] =0; }}// At this point, dp becomes a set of zeros exactly the same as the grid dimension
    // The first thing we need to do is fill in the first row and the first column of the dp as the required distance from the initial position to the target position
    dp[0] [0] = grid[0] [0];
    for (let i = 1; i < rowNum; i++) { dp[i][0] = grid[i][0] + dp[i-1] [0];
    }
    for (let j = 1; j < cowNum; j++) { dp[0][j] = grid[0][j] + dp[0][j-1]}// Through the above two loops we have written the values needed for the first row and first column of the grid to the first and second columns of the DP array
    // Just iterate through the rest of the grid array
    for (let i = 1; i < rowNum; i++) {for (let j = 1; j < cowNum; j++) { dp[i][j] = grid[i][j] +Math.max(dp[i-1][j],dp[i][j-1]); }}// Each value of the dp array should be understood as the sum of the grid array path values
    // the last value of the dp array should be the maximum value
    return dp[rowNum-1][cowNum-1]};` ``
Copy the code