【题目】

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明： 每次只能向下或者向右移动一步。

示例 1：

image.png

输入： grid = [[1,3,1],[1,5,1],[4,2,1]]
输出： 7
解释： 因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入： grid = [[1,2,3],[4,5,6]]
输出： 12

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 200

【题目解析】

解题方法

这个问题可以通过动态规划（Dynamic Programming, DP）来解决。动态规划是一种将复杂问题分解成小问题解决的方法，通过解决子问题，逐步推导出整个问题的最优解。

对于这个问题，我们可以创建一个同样大小的DP数组来存储到达每个格子的最小路径和。对于网格中的每一个格子，只能从上面或者左边移动过来，因此到达该格子的最小路径和就是它上面的格子和左边格子的最小路径和中较小的那一个加上当前格子的值。

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # 获取网格的行数和列数
        m, n = len(grid), len(grid[0])
        
        # 动态规划求解
        for i in range(m):
            for j in range(n):
                # 如果不是起点
                if i != 0 or j != 0:
                    # 如果在网格的最左边，则只能从上面来
                    if j == 0:
                        grid[i][j] += grid[i-1][j]
                    # 如果在网格的最上边，则只能从左边来
                    elif i == 0:
                        grid[i][j] += grid[i][j-1]
                    # 否则，选择从上面来和从左边来的较小者
                    else:
                        grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        # 返回到达网格右下角的最小路径和
        return grid[m-1][n-1]

执行效率

image.png

【总结】

适用问题类型

动态规划算法特别适用于那些问题，其中最优解可以通过决策序列的方式来得到，且每个决策依赖于前一个状态的结果。这类问题通常具有重叠子问题和最优子结构的特点，使得DP算法能够有效减少计算重复，通过局部最优解推导出全局最优解。“最小路径和”问题是一个典型的最优路径问题，要求找到从网格左上角到右下角的最小总和路径，完全符合动态规划适用的问题类型。

解决算法：动态规划

• 算法特点：动态规划的核心在于解决重叠子问题并利用这些子问题的解来构建最终解。该方法通过构建一个DP表（通常是二维数组），其中DP表的每个元素代表到达该位置的最小路径和，从而避免了重复计算，并确保了算法的高效性。
• 时间复杂度与空间复杂度：对于“最小路径和”问题，动态规划算法的时间复杂度为O(mn)，其中m是网格的行数，n是网格的列数，因为需要遍历整个网格来填充DP表。空间复杂度也是O(mn)，因为需要一个同样大小的DP表来存储每个位置的最小路径和。在一些情况下，如果能够原地修改输入网格或者使用滚动数组技巧，空间复杂度可以优化到O(n)或更低。

实践意义

动态规划不仅适用于“最小路径和”这一特定类型的问题，它在算法设计和问题解决中占据着重要地位，能够解决包括但不限于路径问题、序列问题、背包问题等多种类型的问题。掌握动态规划算法，对于提高解决复杂问题的能力、优化程序性能具有重要意义。在软件开发和数据分析领域，动态规划算法的应用范围广泛，从提升算法效率到优化资源分配等方面都发挥着关键作用。

综上所述，通过应用动态规划算法解决“最小路径和”问题，不仅能够有效提升问题解决的效率和质量，还能够深化对动态规划算法设计原理和应用场景的理解。

题目链接

最小路径和