题目地址：
https://leetcode.com/problems/minimum-path-sum/
给定一个矩阵，求从左上到右下所有路径中和最小的那条路径的和。每步只能向右或者向下走。动态规划。设f[i][j]表示从grid[0][0]到grid[i][j]的所有路径中，和最小的那个路径和，那么这条路径有两种可能，一种是从左边来，此时f[i][j]=f[i][j−1]+grid[i][j]，一种是从上边来，此时f[i][j]=f[i−1][j]+grid[i][j]；所以f[i][j]等于这两者较小者。我们可以直接在grid数组上面操作，以节省空间。代码如下：
public class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int n = grid.length, m = grid[0].length;
// 这里采取的是一行一行更新
for (int j = 1; j < m; j++) {
grid[0][j] += grid[0][j - 1];
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < m; j++) {
if (j == 0) {
grid[i][j] += grid[i - 1][j];
} else {
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
}
}
}
return grid[n - 1][m - 1];
}
}
时间复杂度O(mn)，空间O(1)。