Topic describes

Given an M x N grid with non-negative integers, find a path from the top left to the bottom right that minimizes the sum of the numbers along the path. // Note: you can only move one step down or right at a time.Copy the code

Answer key

47. The maximum value of a gift is the same as that of an offer. class Solution { public int minPathSum(int[][] grid) { int row = grid.length, col = grid[0].length; if (row == 0 || col == 0) return 0; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (i == 0 && j == 0) continue; else if (i ! = 0 && j == 0) grid[i][j] += grid[i - 1][j]; else if (i == 0 && j ! = 0) grid[i][j] += grid[i][j - 1]; else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); } } return grid[row - 1][col - 1]; }}Copy the code