动态规划之最小路径和

数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode 力扣 难度
64. Minimum Path Sum 64. 最小路径和 🟠
- 剑指 Offer II 099. 最小路径之和 🟠

———–

今天聊一道经典的动态规划题目，它是力扣第 64 题「 最小路径和」，我来简单描述一下题目：

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

函数签名如下：

int minPathSum(int[][] grid);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int minPathSum(vector<vector<int>>& grid);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def minPathSum(grid: List[List[int]]) -> int

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func minPathSum(grid [][]int) int {}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var minPathSum = function(grid) {
    // function body
};

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

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

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

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

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

我们想计算从起点 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 函数：

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

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def dp(grid: List[List[int]], i: int, j: int) -> int:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func dp(grid [][]int, i int, j int) int {}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var dp = function(grid, i, j) {
  // code logic goes here
}

这个 dp 函数的定义如下：

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

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

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

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    // 计算从左上角走到右下角的最小路径和
    return dp(grid, m - 1, n - 1);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def minPathSum(grid: List[List[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    # 计算从左上角走到右下角的最小路径和
    return dp(grid, m - 1, n - 1)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func minPathSum(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    // 计算从左上角走到右下角的最小路径和
    return dp(grid, m-1, n-1)
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

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

我们可以直接写代码了：

int dp(int[][] grid, int i, int j) {
    // base case
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // 如果索引出界，返回一个很大的值，
    // 保证在取 min 的时候不会被取到
    if (i < 0 || j < 0) {
        return Integer.MAX_VALUE;
    }

    // 左边和上面的最小路径和加上 grid[i][j]
    // 就是到达 (i, j) 的最小路径和
    return Math.min(
            dp(grid, i - 1, j), 
            dp(grid, i, j - 1)
        ) + grid[i][j];
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int dp(vector<vector<int>>& grid, int i, int j) {
    // base case
    if (i == 0 && j == 0) {
        return grid[0][0];
    }
    // 如果索引出界，返回一个很大的值，
    // 保证在取 min 的时候不会被取到
    if (i < 0 || j < 0) {
        return INT_MAX;
    }

    // 左边和上面的最小路径和加上 grid[i][j]
    // 就是到达 (i, j) 的最小路径和
    return min(
            dp(grid, i - 1, j), 
            dp(grid, i, j - 1)
        ) + grid[i][j];
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def dp(grid: List[List[int]], i: int, j: int) -> int:
    # base case
    if i == 0 and j == 0:
        return grid[0][0]

    # 如果索引出界，返回一个很大的值，
    # 保证在取 min 的时候不会被取到
    if i < 0 or j < 0:
        return float('inf')

    # 左边和上面的最小路径和加上 grid[i][j]
    # 就是到达 (i, j) 的最小路径和
    return min(
            dp(grid, i - 1, j), 
            dp(grid, i, j - 1)
        ) + grid[i][j]

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func dp(grid [][]int, i int, j int) int {
    // base case
    if i == 0 && j == 0 {
        return grid[0][0]
    }
    // 如果索引出界，返回一个很大的值，
    // 保证在取 min 的时候不会被取到
    if i < 0 || j < 0 {
        return math.MaxInt32
    }

    // 左边和上面的最小路径和加上 grid[i][j]
    // 就是到达 (i, j) 的最小路径和
    return min(
            dp(grid, i - 1, j), 
            dp(grid, i, j - 1)
        ) + grid[i][j]
}

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var dp = function(grid, i, j) {
  // base case
  if (i == 0 && j == 0) {
    return grid[0][0];
  }
  // 如果索引出界，返回一个很大的值，
  // 保证在取 min 的时候不会被取到
  if (i < 0 || j < 0) {
    return Number.MAX_VALUE;
  }
  
  // 左边和上面的最小路径和加上 grid[i][j]
  // 就是到达 (i, j) 的最小路径和
  return Math.min(
    dp(grid, i - 1, j), 
    dp(grid, i, j - 1)
  ) + grid[i][j];
}

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

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

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

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

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

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

class Solution {
    // 备忘录
    int[][] memo;

    int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // 构造备忘录，初始值全部设为 -1
        memo = new int[m][n];
        for (int[] row : memo)
            Arrays.fill(row, -1);
        
        return dp(grid, m - 1, n - 1);
    }

    int dp(int[][] grid, int i, int j) {
        // base case
        if (i == 0 && j == 0) {
            return grid[0][0];
        }
        if (i < 0 || j < 0) {
            return Integer.MAX_VALUE;
        }
        // 避免重复计算
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        // 将计算结果记入备忘录
        memo[i][j] = Math.min(
            dp(grid, i - 1, j),
            dp(grid, i, j - 1)
        ) + grid[i][j];

        return memo[i][j];
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
private:
    //备忘录
    vector<vector<int>> memo;

    int dp(vector<vector<int>> &grid, int i, int j) {
        //base case
        if (i == 0 && j == 0) {
            return grid[0][0];
        }
        if (i < 0 || j < 0) {
            return INT_MAX;
        }
        //避免重复计算
        if (memo[i][j] != -1) {
            return memo[i][j];
        }
        //将计算结果记入备忘录
        memo[i][j] = min(
            dp(grid, i - 1, j),
            dp(grid, i, j - 1)
        ) + grid[i][j];

        return memo[i][j];
    }

public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        //构造备忘录，初始值全部设为 -1
        memo = vector<vector<int>>(m, vector<int>(n, -1));
        return dp(grid, m - 1, n - 1);
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        # 构造备忘录，初始值全部设为 -1
        memo = [[-1 for _ in range(n)] for _ in range(m)]

        def dp(i, j):
            # base case
            if i == 0 and j == 0:
                return grid[0][0]
            if i < 0 or j < 0:
                return float('inf')
            # 避免重复计算
            if memo[i][j] != -1:
                return memo[i][j]
            # 将计算结果记入备忘录
            memo[i][j] = min(
                dp(i - 1, j),
                dp(i, j - 1)
            ) + grid[i][j]

            return memo[i][j]
        
        return dp(m - 1, n - 1)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func minPathSum(grid [][]int) int {
    // 构造备忘录
    memo := make([][]int, len(grid))
    for i := range memo {
        memo[i] = make([]int, len(grid[0]))
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }

    return dp(grid, len(grid)-1, len(grid[0])-1, memo)
}

func dp(grid [][]int, i int, j int, memo [][]int) int {
    // base case
    if i == 0 && j == 0 {
        return grid[0][0]
    }
    if i < 0 || j < 0 {
        return math.MaxInt32
    }
    // 避免重复计算
    if memo[i][j] != -1 {
        return memo[i][j]
    }
    // 将计算结果记入备忘录
    memo[i][j] = int(math.Min(
        float64(dp(grid, i-1, j, memo)),
        float64(dp(grid, i, j-1, memo)),
    )) + grid[i][j]

    return memo[i][j]
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var minPathSum = function(grid) {
    // 备忘录
    const memo = [];

    const dp = function(i, j) {
        // base case
        if (i === 0 && j === 0) {
            return grid[0][0];
        }
        if (i < 0 || j < 0) {
            return Number.MAX_SAFE_INTEGER;
        }
        // 避免重复计算
        if (memo[i] && memo[i][j] !== undefined) {
            return memo[i][j];
        }
        // 构造备忘录，初始值全部设为 -1
        memo[i] = memo[i] || [];
        memo[i][j] = Math.min(
            dp(i - 1, j),
            dp(i, j - 1)
        ) + grid[i][j];

        return memo[i][j];
    }

    return dp(grid.length - 1, grid[0].length - 1);
};
🍭 代码可视化动画 🍭

至此，本题就算是解决了，时间复杂度和空间复杂度都是 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];
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    
    /**** 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] = min(
                dp[i - 1][j],
                dp[i][j - 1]
            ) + grid[i][j];
        }
    }
    
    return dp[m - 1][n - 1];
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

def minPathSum(grid: List[List[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    dp = [[0] * n for _ in range(m)]

    # base case
    dp[0][0] = grid[0][0]    
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] + grid[0][j]

    # 状态转移
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

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

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func minPathSum(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])
    dp := make([][]int, m)
    for i := 0; i < m; i++ {
        dp[i] = make([]int, n)
    }

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

    for i := 1; i < m; i++ {
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    }

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

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

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var minPathSum = function(grid) {
    var m = grid.length;
    var n = grid[0].length;
    var dp = new Array(m).fill().map(() => new Array(n));

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

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

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

    // 状态转移
    for (var i = 1; i < m; i++) {
        for (var 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] 的值怎么算呢？其实很简单，第一行和第一列的路径和只有下面这一种情况嘛：

那么按照 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 数组的技巧，这里也是适用的，不过略微复杂些，本文由于篇幅所限就不写了，有兴趣的读者可以自己尝试一下。

本文到此结束，下篇文章写一道进阶题目，更加巧妙和有趣，敬请期待~

引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：

LeetCode 力扣
- 剑指 Offer 47. 礼物的最大价值
- 剑指 Offer II 099. 最小路径之和
引用本文的文章

＿＿＿＿＿＿＿＿＿＿＿＿＿

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释