企业官网建设流程全解析

一、二维 DP 基础认知

1. 核心概念

用 二维数组dp[i][j]描述网格位置的状态，对应二维坐标问题（迷宫、路径、矩阵、子序列等）。 依旧遵循 DP 四步解题法：状态定义 → 初始化 → 状态转移 → 结果输出。

2. 通用前提

机器人 / 行走规则：仅能向右、向下移动（本系列通用规则）。

二、题型 1：不同路径（LeetCode 62 基础版）

题目描述

m行n列网格，机器人从左上角(0,0)走到右下角(m-1,n-1)，只能向右 / 向下走，求总路径数。

解题推导

1. 状态定义dp[i][j]：从起点走到坐标(i,j)的路径总数。
2. 初始边界

• 第一行：只能一直右走，dp[0][j] = 1
• 第一列：只能一直下走，dp[i][0] = 1

1. 状态转移方程当前位置只能从 ** 上方(i-1,j)或左方(i,j-1)** 走来： \(dp[i][j] = dp[i-1][j] + dp[i][j-1]\)

完整代码（二维数组版）

#include <iostream> #include <vector> using namespace std; int uniquePaths(int m, int n) { vector<vector<int>> dp(m, vector<int>(n, 0)); // 初始化第一行 for(int j = 0; j < n; j++) dp[0][j] = 1; // 初始化第一列 for(int i = 0; i < m; i++) dp[i][0] = 1; // 状态递推 for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; }

空间优化（一维滚动数组 O (n)）

当前行仅依赖上一行数据，用一维数组滚动更新，缩减空间：

int uniquePathsOpt(int m, int n) { vector<int> dp(n, 1); for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { dp[j] = dp[j] + dp[j-1]; } } return dp[n-1]; }

三、题型 2：不同路径 II（LeetCode 63 含障碍物）

题目变化

网格中存在障碍物1，无法通行；空位置为0，有障碍物的位置路径数为 0。

解题要点

1. 初始化时：障碍物所在位置及后续位置，路径数置 0
2. 递推时：遇到障碍物直接跳过，dp[i][j] = 0

完整代码

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); vector<vector<int>> dp(m, vector<int>(n, 0)); // 初始化第一行 for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1; // 初始化第一列 for(int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1; for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { // 遇到障碍物，路径数为0 if(obstacleGrid[i][j] == 1) dp[i][j] = 0; else dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; }

四、题型 3：最小路径和（LeetCode 64 进阶变种）

题目描述

网格每个位置有非负权值，从左上角走到右下角，只能右 / 下移动，求路径经过数字的最小总和。

解题推导

1. 状态定义dp[i][j]：走到(i,j)位置的最小路径和。
2. 初始边界

• 第一行：只能右走，累加前缀和
• 第一列：只能下走，累加前缀和

1. 状态转移方程\(dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]\)

完整代码

#include <algorithm> int minPathSum(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<vector<int>> dp(m, vector<int>(n)); dp[0][0] = grid[0][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++) dp[i][0] = dp[i-1][0] + grid[i][0]; // 递推计算 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]; }

五、三类二维路径题核心对比

六、二维 DP 通用解题步骤

1. 定义dp[i][j]含义，绑定网格坐标
2. 单独初始化第一行、第一列（边界只能单方向移动）
3. 双层循环遍历剩余网格，套用转移方程
4. 特殊判断：障碍物、越界、极值选取
5. 最终结果取dp[m-1][n-1]

七、空间优化思路总结

1. 标准写法：二维数组O(m*n)，逻辑直观，新手首选
2. 滚动数组：一维数组O(n)，利用行覆盖特性，面试常用优化方案
3. 原地修改：直接在原grid数组上计算，额外空间O(1)（不建议，会破坏原数据）

八、新手易错点

1. 边界初始化不全，第一行 / 第一列漏处理
2. 障碍物题目中，障碍物之后的位置错误赋值为 1
3. 最小路径和混淆min与求和逻辑
4. 行列下标m/n颠倒，数组越界

九、今日总结

1. 二维 DP 适配网格、矩阵类问题，核心是dp[i][j]坐标状态定义
2. 路径类题目通用移动规则：仅向右、向下
3. 基础路径、障碍路径、最小路径和是二维 DP 入门三大必背模板
4. 掌握一维滚动数组优化，提升代码性能