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.

题目大意

给定二维数组，一个机器人从左上角开始，每次只能往右或者往下走，问到达长方形最左下角时，所走路径最小数字和是多少？

思路

很明显是一个二维的动态规划题。动态规划最重要的就是要找到递推式，将当前的大问题划分为更小的子问题。

以3x7的格子为例，对于坐标为(2,5)的格子，只有可能是从上面(1,5)或者左边(2,4)的格子到达的。所以我们只需要选出到(2,4)和(1,5)两个格子的最小路径和中较小的那一个，之后在加上(2,5)本身的数字即为到达(2,5)的最小路径和。这样我们就得到了递推式

1
D(i, j) = A(i, j) + min(D(i - 1, j), D(i, j - 1))

当然我们还需要考虑一些特殊情况。当格子在第一行即i = 0时，只能由左边的格子到达；当格子在第一列即j = 0时，只能由上方的格子到达。这两种特殊情况中的格子都只需要加上对应的上方或者左边的路径和即可。

这种思路需要使用m x n的空间用来存储到达所有格子的最小路径和，但是数组已经给定了，因此空间复杂度为O(1)。我们需要遍历整个格子，因此时间复杂度是O(m*n)。Java版的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int minPathSum(int[][] grid) {
        for (int i = 1; i < grid[0].length; i++) {
            grid[0][i] += grid[0][i - 1];
        }
        
        for (int i = 1; i < grid.length; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

Leetcode提交运行时间为4ms

提交结果
提交结果