题目

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

自底向上的动态规划 $O(mn)$

7   22  9   13  3   16  MAX
21  19  1   10  5   6   MAX
18  2   24  15  14  17  MAX
8   23  4   11  12  20  0       # 注意，这里必须是0。
MAX MAX MAX MAX MAX 0   MAX

# 这里也必须是0


代码

public class Solution {
public int minPathSum(int[][] grid) {
int lineSize = grid.length;
if (lineSize == 0) { return 0; }
int columnSize = grid[0].length;
if (columnSize == 0) { return 0; }
int[][] memo = new int[lineSize+1][columnSize+1]; // 最后多加一行一列哨兵。
for (int i = 0; i < lineSize+1; i++) {
memo[i][columnSize] = Integer.MAX_VALUE;
}
for (int i = 0; i < columnSize+1; i++) {
memo[lineSize][i] = Integer.MAX_VALUE;
}
memo[lineSize-1][columnSize] = 0; // 为了不影响点[i][j]
memo[lineSize][columnSize-1] = 0; // 为了不影响点[i][j]
for (int i = lineSize-1; i >= 0; i--) {
for (int j = columnSize-1; j >= 0; j--) {
memo[i][j] = grid[i][j] + Math.min(memo[i+1][j],memo[i][j+1]); // 哨兵的作用显现出来，所有点都一般化处理。
}
}
return memo[0][0];
}
}