🗺️ 路径DP — 最小路径和与不同路径

📖 网格路径DP概览

网格路径DP是最直观的DP模型：在m*n的网格中从左上角走到右下角，每步只能向右或向下。核心状态定义：dp[i][j] = 到达位置(i,j)的某个属性（最小和、路径数等）。

1. 网格DP的通用框架

def grid_dp(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]  # 只能从左来
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]  # 只能从上来
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = f(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    return dp[m-1][n-1]

🔬 题目一：最小路径和（LC 64）

给定m*n的非负整数网格，找到从左上到右下的路径，使路径上数字之和最小。

思路分析

代码实现

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        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]

# 原地修改版本 O(1)空间
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for j in range(1, n):
            grid[0][j] += grid[0][j-1]
        for i in range(1, m):
            grid[i][0] += grid[i-1][0]
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        return grid[m-1][n-1]

复杂度分析

时间: O(m * n) 空间: O(m * n)，原地修改O(1)

🔬 题目二：不同路径（LC 62）

一个m*n的网格，从左上到右下有多少条不同路径？

思路分析

代码实现

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

# 组合数学版本
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        from math import comb
        return comb(m + n - 2, m - 1)

复杂度分析

时间: O(m * n) 空间: O(m * n)，可优化到O(n)

🔬 题目三：不同路径II（LC 63）

网格中有障碍物，求从左上到右下的不同路径数。

思路分析

代码实现

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] if obstacleGrid[0][j] == 0 else 0
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] if obstacleGrid[i][0] == 0 else 0
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

复杂度分析

时间: O(m * n) 空间: O(m * n)

面试实战技巧

在实际面试中，算法题不仅仅是写代码，更考察沟通、分析和解决问题的能力。以下是一些实战技巧：

1. 解题步骤模板

2. 常见陷阱

3. 代码模板

# 通用解题模板
class Solution:
    def solve(self, input_data):
        # 1. 边界检查
        if not input_data:
            return default_value
        # 2. 初始化
        result = initial_value
        state = initial_state
        # 3. 主循环
        for item in input_data:
            state = transition(state, item)
            result = max/min/update(result, state)
        # 4. 返回结果
        return result

📝 课后练习

1. LC 120 三角形最小路径和
2. LC 931 下降路径最小和
3. LC 174 地下城游戏（反向DP）
4. LC 1289 下降路径最小和II

🔑 本课要点回顾

• 网格DP通用框架：初始化边+双重循环填表
• 最小路径和：dp[i][j]=min(上,左)+当前
• 不同路径：dp[i][j]=dp[上]+dp[左]（加法原理）
• 障碍处理：障碍位置dp=0
• 网格DP本质是DAG上的最短路/路径计数

📚 扩展阅读

• 算法导论 DP章节
• LeetCode路径DP专题
• 网格路径可视化

⚡ 进阶专题：常见变体与扩展

每道经典题目都有丰富的变体。掌握核心模板后，灵活应对变体才是面试的真正挑战。以下列举本课相关的高频变体和扩展思路。

1. 常见题目变体

2. 面试中的沟通技巧

# 面试沟通模板
# 1. 先说思路（1-2分钟）
"这道题我想到两种解法，先说更直观的一种..."

# 2. 分析复杂度（30秒）
"时间复杂度O(n^2)，空间可以优化到O(n)"

# 3. 边写边说
"这里我定义dp[i]表示...，转移方程是..."

# 4. 主动验证
"我用示例走一遍：dp[0]=..., dp[1]=..."

# 5. 讨论优化
"空间还可以进一步优化，因为dp[i]只依赖..."

3. 代码调试检查清单

⚡ 路径DP变形大全

网格路径DP的变形非常丰富，以下是最常见的变体。

为什么LC 174需要反向DP？