网格图动态规划：从路径计数到最优路径求解

1. 从一维到二维：网格图DP模型

动态规划（Dynamic Programming）是算法设计中的核心思想之一，而网格图DP则是其中最具代表性的应用场景。作为从一维DP向二维DP过渡的重要桥梁，网格图问题能帮助我们建立空间思维，理解状态转移的本质。

在解决实际问题时，我们经常会遇到需要在网格矩阵中寻找最优路径的情况。这类问题通常具有以下特征：

• 移动方向受限（如只能向右或向下）
• 每个网格点有特定属性（如障碍物、权重值等）
• 需要计算路径数量或最优路径值

2. 网格图DP基础概念

2.1 什么是网格图模型？

网格图模型可以看作是一个m×n的棋盘，我们需要从起点（通常是左上角）出发，按照特定移动规则到达终点（通常是右下角）。在这个过程中，我们需要解决三类典型问题：

1. 路径计数：计算从起点到终点的所有可能路径数量
2. 最值路径：寻找使某种指标（如路径和）最大或最小的路径
3. 约束路径：在特定约束条件下（如不能经过某些点）寻找路径

2.2 核心解题套路

解决网格DP问题有五个标准步骤：

1. 状态定义：明确dp[i][j]表示什么含义
2. 状态转移方程：确定如何从子问题推导当前状态
3. 初始化：处理边界条件的初始值
4. 填表顺序：确定计算状态的先后顺序
5. 返回值：确定最终结果对应的状态

其中有两个特别重要的技巧：

• 虚拟边框技巧：通过多开一行一列来简化边界条件处理
• 空间优化技巧：有时可以将二维DP优化为一维，减少空间复杂度

3. 基础篇：路径计数问题

3.1 不同路径（LeetCode 62）

3.1.1 问题描述

一个机器人位于m×n网格的左上角，每次只能向下或向右移动一步，问到达右下角有多少种不同的路径。

3.1.2 解题思路

1. 状态定义：
   dp[i][j]表示走到(i,j)位置的不同路径数

2. 状态转移：
   由于只能从上方或左方过来，所以：
   dp[i][j] = dp[i-1][j] + dp[i][j-1]

3. 初始化技巧：
   使用虚拟边框，将dp[0][1]设为1作为"引子"，这样：
   dp[1][1] = dp[0][1] + dp[1][0] = 1 + 0 = 1

3.1.3 代码实现

cpp复制class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        dp[0][1] = 1; // 初始化技巧
        
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                dp[i][j] = dp[i