题目
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
解题
分析
这道题，我能想到的一共三种解法。
首先，这很类似与迷宫的问题，很显然可以使用递归来解决，我们可以把所有可能到达右下角最后一个元素的路线的权值和都计算出来，然后取最小的一个。可以优化在递归的过程中，就记录最小值，某条路径递归的一半就比这个最小值大或者小，那么我们就终止递归。
这种方式的时间复杂度为O（2^m+n）,空间复杂度为为O（m+n）
第二种，这道题很显然是一个动态规划的问题，到达最后一个元素（n，m）的最短路径，要取决于到达（n - 1，m）和（n，m - 1）的元素的最短路径，如果要求不破坏原有的数据，我们可以再定义一个同样大小的二维数组，从最后一行开始，从后往前遍历所有的元素，每一个元素都记录右下角到这个节点的最短路径，最后返回（0，0）个元素就可以了。（一维数组也可以实现）
这种方式的时间复杂度为O（mn）,空间复杂度为为O（mn）（一维数组的话空间复杂度为O（m））
如果不需要保留原来的数据结构，我们可以在题目中的二维数组直接修改，这样空间复杂度为O（1）
代码
第一种-递归优化版本
class Solution {
// 记录当前的最小值
int min = -1;
public int minPathSum(int[][] grid) {
recursive(grid, 0, 0, grid[0][0]);
return min;
}
private void recursive(int[][] grid, int i, int j, int sum) {
// 中断递归的条件,否则会超时
if (min != -1 && sum >= min) {
return;
}
if (i == grid.length - 1 && j == grid[0].length - 1) {
min = sum;
return;
}
// 优先向下走
if (i < grid.length - 1) {
recursive(grid, i + 1, j, sum + grid[i + 1][j]);
}
// 上路走不通再向下走
if (j < grid[0].length - 1) {
recursive(grid, i, j + 1, sum + grid[i][j + 1]);
}
}
}
第二种-二维数组动态规划
class Solution {
public int minPathSum(int[][] grid) {
int[][] dp = new int[grid.length][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[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
} else if (i == grid.length - 1 && j < grid[0].length - 1) {
dp[i][j] = dp[i][j + 1] + grid[i][j];
} else if (i < grid.length - 1 && j == grid[0].length - 1) {
dp[i][j] = dp[i + 1][j] + grid[i][j];
} else {
dp[i][j] = grid[i][j];
}
}
}
return dp[0][0];
}
}
第三种-动态规划-原地修改
class Solution {
public int minPathSum(int[][] grid) {
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) {
grid[i][j] = Math.min(grid[i + 1][j], grid[i][j + 1]) + grid[i][j];
} else if (i == grid.length - 1 && j < grid[0].length - 1) {
grid[i][j] = grid[i][j + 1] + grid[i][j];
} else if (i < grid.length - 1 && j == grid[0].length - 1) {
grid[i][j] = grid[i + 1][j] + grid[i][j];
}
}
}
return grid[0][0];
}
}