题目: 最小路径和

分析

方法一：暴力递归

最简单的方法是使用递归进行暴力求解，从左上角开始递归到右下角，计算所有可能的路径和，返回最小值。代码如下：

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    def dfs(i, j):
        if i == m-1 and j == n-1:
            return grid[i][j]
        if i == m-1:
            return grid[i][j] + dfs(i, j+1)
        if j == n-1:
            return grid[i][j] + dfs(i+1, j)
        return grid[i][j] + min(dfs(i+1, j), dfs(i, j+1))
    return dfs(0, 0)

时间复杂度：$O(2^{m+n})$。

方法二：记忆化搜索

在方法一的基础上，我们可以加上记忆化，避免重复计算。我们使用一个 $m \times n$ 的二维数组 memo 来记录每个状态的值，如果该状态已经计算过，直接返回。代码如下：

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    memo = [[-1] * n for _ in range(m)]
    def dfs(i, j):
        if memo[i][j] != -1:
            return memo[i][j]
        if i == m-1 and j == n-1:
            memo[i][j] = grid[i][j]
        elif i == m-1:
            memo[i][j] = grid[i][j] + dfs(i, j+1)
        elif j == n-1:
            memo[i][j] = grid[i][j] + dfs(i+1, j)
        else:
            memo[i][j] = grid[i][j] + min(dfs(i+1, j), dfs(i, j+1))
        return memo[i][j]
    return dfs(0, 0)

时间复杂度：$O(mn)$。

方法三：动态规划

使用动态规划，我们可以通过建立一个 $m \times n$ 的二维数组 dp 来记录从起点到当前位置的最小路径和。对于每个位置 $(i, j)$，可以通过从左边或上边转移过来得到最小路径和。因此，状态转移方程为：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。代码如下：

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    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