它是力扣第 64 题，我来简单描述一下题目：

现在给你输入一个二维数组grid，其中的元素都是非负整数，现在你站在左上角，只能向右或者向下移动，需要到达右下角。现在请你计算，经过的路径和最小是多少？

函数签名如下：

  1. int minPathSum(int[][] grid);

比如题目举的例子，输入如下的grid数组：

最小路径和 - 图1

算法应该返回 7，最小路径和为 7，就是上图黄色的路径。

其实这道题难度不算大，但我们刷题群里很多朋友讨论，而且这个问题还有一些难度比较大的变体，所以讲一下这种问题的通用思路。

一般来说，让你在二维矩阵中求最优化问题（最大值或者最小值），肯定需要递归 + 备忘录，也就是动态规划技巧。

就拿题目举的例子来说，我给图中的几个格子编个号方便描述：

最小路径和 - 图2

我们想计算从起点D到达B的最小路径和，那你说怎么才能到达B呢？

题目说了只能向右或者向下走，所以只有从A或者C走到B。

那么算法怎么知道从A走到B才能使路径和最小，而不是从C走到B呢？

难道是因为位置A的元素大小是 1，位置C的元素是 2，1 小于 2，所以一定要从A走到B才能使路径和最小吗？

其实不是的，真正的原因是，从**D**走到**A**的最小路径和是 6，而从**D**走到**C**的最小路径和是 8，6 小于 8，所以一定要从**A**走到**B**才能使路径和最小。

换句话说，我们把「从D走到B的最小路径和」这个问题转化成了「从D走到A的最小路径和」和 「从D走到C的最小路径和」这两个问题。

理解了上面的分析，这不就是状态转移方程吗？所以这个问题肯定会用到动态规划技巧来解决。

自顶向下解法

比如我们定义如下一个dp函数：

  1. int dp(int[][] grid, int i, int j);

这个dp函数的定义如下：

从左上角位置**(0, 0)**走到位置**(i, j)**的最小路径和为**dp(grid, i, j)**。

根据这个定义，我们想求的最小路径和就可以通过调用这个dp函数计算出来：

  1. int minPathSum(int[][] grid) {
  2.     int m = grid.length;
  3.     int n = grid[0].length;
  4.     // 计算从左上角走到右下角的最小路径和
  5.     return dp(grid, m - 1, n - 1);
  6. }

再根据刚才的分析，很容易发现，dp(grid, i, j)的值取决于dp(grid, i - 1, j)和dp(grid, i, j - 1)返回的值。

我们可以直接写代码了：

  1. int dp(int[][] grid, int i, int j) {
  2.     // base case
  3.     if (i == 0 && j == 0) {
  4.         return grid[0][0];
  5.     }
  6.     // 如果索引出界，返回一个很大的值，
  7.     // 保证在取 min 的时候不会被取到
  8.     if (i < 0 || j < 0) {
  9.         return Integer.MAX_VALUE;
  10.     }
  12.     // 左边和上面的最小路径和加上 grid[i][j]
  13.     // 就是到达 (i, j) 的最小路径和
  14.     return Math.min(
  15.             dp(grid, i - 1, j), 
  16.             dp(grid, i, j - 1)
  17.         ) + grid[i][j];
  18. }

上述代码逻辑已经完整了，接下来就分析一下，这个递归算法是否存在重叠子问题？是否需要用备忘录优化一下执行效率？

前文多次说过判断重叠子问题的技巧，首先抽象出上述代码的递归框架：

  1. int dp(int i, int j) {
  2.     dp(i - 1, j); // #1
  3.     dp(i, j - 1); // #2
  4. }

如果我想从dp(i, j)递归到dp(i-1, j-1)，有几种不同的递归调用路径？

可以是dp(i, j) -> #1 -> #2或者dp(i, j) -> #2 -> #1，不止一种，说明dp(i-1, j-1)会被多次计算，所以一定存在重叠子问题。

那么我们可以使用备忘录技巧进行优化：

  1. int[][] memo;
  3. int minPathSum(int[][] grid) {
  4.     int m = grid.length;
  5.     int n = grid[0].length;
  6.     // 构造备忘录，初始值全部设为 -1
  7.     memo = new int[m][n];
  8.     for (int[] row : memo)
  9.         Arrays.fill(row, -1);
  11.     return dp(grid, m - 1, n - 1);
  12. }
  15. int dp(int[][] grid, int i, int j) {
  16.     // base case
  17.     if (i == 0 && j == 0) {
  18.         return grid[0][0];
  19.     }
  20.     if (i < 0 || j < 0) {
  21.         return Integer.MAX_VALUE;
  22.     }
  23.     // 避免重复计算
  24.     if (memo[i][j] != -1) {
  25.         return memo[i][j];
  26.     }
  27.     // 将计算结果记入备忘录
  28.     memo[i][j] = Math.min(
  29.         dp(grid, i - 1, j),
  30.         dp(grid, i, j - 1)
  31.     ) + grid[i][j];
  33.     return memo[i][j];
  34. }

至此，本题就算是解决了，时间复杂度和空间复杂度都是O(MN)，标准的自顶向下动态规划解法。

自底向上解法

有的读者可能问，能不能用自底向上的迭代解法来做这道题呢？完全可以的。

首先，类似刚才的dp函数，我们需要一个二维dp数组，定义如下：

从左上角位置**(0, 0)**走到位置**(i, j)**的最小路径和为**dp[i][j]**。

状态转移方程当然不会变的，dp[i][j]依然取决于dp[i-1][j]和dp[i][j-1]，直接看代码吧：

int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];

        /**** base case ****/
        dp[0][0] = grid[0][0];

        for (int i = 1; i < m; i++)
            dp[i][0] = dp[i - 1][0] + grid[i][0];

        for (int j = 1; j < n; j++)
            dp[0][j] = dp[0][j - 1] + grid[0][j];        
        /*******************/

        // 状态转移
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(
                    dp[i - 1][j],
                    dp[i][j - 1]
                ) + grid[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }

这个解法的 base case 看起来和递归解法略有不同，但实际上是一样的。

因为状态转移为下面这段代码：

dp[i][j] = Math.min(
    dp[i - 1][j],
    dp[i][j - 1]
) + grid[i][j];

那如果i或者j等于 0 的时候，就会出现索引越界的错误。

所以我们需要提前计算出dp[0][..]和dp[..][0]，然后让i和j的值从 1 开始迭代。

dp[0][..]和dp[..][0]的值怎么算呢？其实很简单，第一行和第一列的路径和只有下面这一种情况嘛：

最小路径和 - 图3

那么按照dp数组的定义，dp[i][0] = sum(grid[0..i][0]), dp[0][j] = sum(grid[0][0..j])，也就是如下代码：

/**** base case ****/
dp[0][0] = grid[0][0];

for (int i = 1; i < m; i++)
    dp[i][0] = dp[i - 1][0] + grid[i][0];

for (int j = 1; j < n; j++)
    dp[0][j] = dp[0][j - 1] + grid[0][j];        
/*******************/

到这里，自底向上的迭代解法也搞定了，那有的读者可能又要问了，能不能优化一下算法的空间复杂度呢？前文说过降低dp数组的技巧，这里也是适用的，不过略微复杂些。

int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> dp(n,0);
        /**** base case ****/
        dp[0] = grid[0][0];
        for(int j = 1;j<n;++j){
            dp[j] = dp[j-1]+grid[0][j];
        }
        // 状态转移
        for (int i = 1; i < m; i++) {
            dp[0] = dp[0] + grid[i][0];
            for (int j = 1; j < n; j++) {
                dp[j] = min(dp[j],dp[j-1]) + grid[i][j];
            }
        }
        return dp[n - 1];
    }