64. 最小路径和
难度中等802
给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**每次只能向下或者向右移动一步。
示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。package com.nie.o2;/* * *@auth wenzhao *@date 2021/2/25 11:31 */
public class LEE64 {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int[][] dp = new int[rows][cols];
dp[0][0] = grid[0][0];
for (int i = 1; i < rows; i ) {
dp[i][0] = dp[i - 1][0] dp[i][0];
}
for (int i = 1; i < cols; i ) {
dp[0][i] = dp[0][i - 1] dp[0][i];
}
for (int i = 1; i < rows; i ) {
for (int j = 1; j < cols; j ) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) grid[i][j];
}
}
return dp[rows - 1][cols - 1];
}
public int minPathSum1(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int[] dp = new int[grid[0].length];
for (int i = grid.length - 1; i >= 0; i--) {
for (int j = grid[0].length - 1; j >= 0; j--) {
if (i == grid.length - 1 && j != grid[0].length - 1) {
dp[j] = grid[i][j] dp[j 1];
} else if (i != grid.length - 1 && j == grid[0].length - 1) {
dp[j] = grid[i][j] dp[j];
} else if (i != grid.length - 1 && j != grid[0].length - 1) {
dp[j] = grid[i][j] Math.min(dp[j], dp[j 1]);
} else {
dp[j] = grid[i][j];
}
}
}
return dp[0];
}
}
