算法精讲--动态规划（二）：多维DP与状态压缩技巧

无限大

1446人浏览 · 2025-02-20 15:37:23

无限大 · 2025-02-20 15:37:23 发布

🚀 算法精讲–动态规划（二）：多维DP与状态压缩技巧

📚 上期回顾：[算法精讲–动态规划（一）：基础与核心思想] 中我们掌握了单序列DP的核心解法，本期将解锁更复杂的场景！

🌟 核心知识图谱

一、🔮 多维DP入门指南

1.1 什么是多维DP？ 🤔

多维DP是动态规划的进阶形态，通过多维状态定义描述更复杂的决策过程：

# 单序列DP（一维）
dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 

# 多维DP（二维经典）
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

核心区别 ：

	单序列DP	多维DP
状态维度	👉 一维数组	👉 二维/三维数组
适用场景	🎯 线性序列问题	🎯 网格/矩阵问题
转移复杂度	⚡ 相对简单	⚡ 多方向转移
经典问题	打家劫舍	编辑距离

1.2 多维DP四步心法（在面对多维问题时怎样选择） 🚀

1️⃣ 状态定义维度选择

// 二维场景：网格路径问题
int[][] dp = new int[m][n]; // 表示走到(i,j)的最小路径和

// 三维场景：股票交易
int[][][] dp = new int[n][k][2]; // [天数][交易次数][持股状态]

2️⃣ 状态转移多向推导

3️⃣ 初始化边界技巧

# 首行首列特殊处理
for i in range(m):
    dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(n):
    dp[0][j] = dp[0][j-1] + grid[0][j]

4️⃣ 遍历顺序选择

// 正序更新：适用于无后效性问题
for (int i=1; i<m; i++) {
    for (int j=1; j<n; j++) {
        dp[i][j] = ...
    }
}

// 逆序更新：适用于背包类问题
for (int i=m-1; i>=0; i--) {
    for (int j=n-1; j>=0; j--) {
        dp[i][j] = ...
    }
}

1.3 何时选择多维DP？ 🔍

当问题具有以下特征时需考虑多维DP：

🎯 双重约束条件 ：如背包问题中的重量+体积限制
🎯 空间移动特征 ：如棋盘类问题的行列坐标
🎯 状态叠加需求 ：如股票交易中的天数+交易次数+持股状态

二、🔍 具体习题

具体的解题思路请看博文：算法精讲–动态规划四步法则，方法依旧如同上期当中的内容，通过四步法则来进行解题。

1.1 编辑距离（72. 编辑距离）

🛠️ 四维分析法：

状态定义 dp[i][j] 表示将 word1 前 i个字符转换为 word2 前 j个字符的最小代价
```
int[][] dp = new int[m+1][n+1]; // Java数组初始化
```
状态转移方程推导

操作类型转移方向代价计算
删除 i-1 → i dp[i][j] = dp[i-1][j] + 1
插入 j-1 → j dp[i][j] = dp[i][j-1] + 1
替换 i-1,j-1 → i,j dp[i][j] = dp[i-1][j-1] + cost

操作类型	转移方向	代价计算
删除	`i-1` → `i`	`dp[i][j] = dp[i-1][j] + 1`
插入	`j-1` → `j`	`dp[i][j] = dp[i][j-1] + 1`
替换	`i-1,j-1` → `i,j`	`dp[i][j] = dp[i-1][j-1] + cost`

Java实现（含滚动数组优化）

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[] prev = new int[n+1];
    for (int j=0; j<=n; j++) prev[j] = j;

    for (int i=1; i<=m; i++) {
        int[] curr = new int[n+1];
        curr[0] = i;
        for (int j=1; j<=n; j++) {
            if (word1.charAt(i-1) == word2.charAt(j-1)) {
                curr[j] = prev[j-1];
            } else {
                curr[j] = Math.min(Math.min(prev[j], curr[j-1]), prev[j-1]) + 1;
            }
        }
        prev = curr;
    }
    return prev[n];
}

1.2 不同路径（62. 不同路径）

🔍 状态转移深层解析：

Java实现（二维压缩为一维）

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1); // 第一行初始化
  
    for (int i=1; i<m; i++) {
        for (int j=1; j<n; j++) {
            dp[j] += dp[j-1]; // 滚动更新
        }
    }
    return dp[n-1];
}

三维扩展案例：股票交易中的三维状态
dp[i][k][0] 表示第 i天完成 k次交易后不持有股票的最大收益

三、⚡ 状态压缩四大心法

3.1 滚动数组法

📌 适用场景：行间无后效性
🎯 典型例题：120. 三角形最小路径和

// Java实现滚动数组
public int minimumTotal(List<List<Integer>> triangle) {
    int[] dp = new int[triangle.size()+1];
    for (int i=triangle.size()-1; i>=0; i--) {
        for (int j=0; j<triangle.get(i).size(); j++) {
            dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
        }
    }
    return dp[0];
}

3.2 位运算压缩

📌 处理集合状态类问题
🎯 典型例题：847. 访问所有节点的最短路径

// 状态编码示例
int state = 0;
state |= (1 << node); // 标记节点已访问

3.3 二进制掩码法

📌 处理排列组合问题
🎯 典型例题：351. 安卓系统手势解锁

// 状态转移核心代码
int mask = 1 << 9; // 9个点的状态存储
if ((visited & (1 << next)) == 0) { // 检查是否访问过
    newState = visited | (1 << next); // 更新状态
}

3.4 分层压缩法

📌 处理三维DP优化
🎯 典型例题：188. 买卖股票的最佳时机 IV

// 三维压缩为二维
int[][] dp = new int[k+1][2];
for (int i=1; i<=n; i++) {
    for (int j=k; j>=1; j--) {
        dp[j][0] = Math.max(dp[j][0], dp[j][1] + prices[i]);
        dp[j][1] = Math.max(dp[j][1], dp[j-1][0] - prices[i]);
    }
}

四、📝 实战训练营思路分析解析

案例1：不同路径 II（63. 不同路径 II）

分步代码解析：

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    int[] dp = new int[n];
    dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1; // 🚩关键初始化
  
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            if (obstacleGrid[i][j] == 1) {
                dp[j] = 0; // ❗遇到障碍物清零
            } else if (j > 0 && i == 0) { 
                dp[j] = dp[j-1]; // ➡️第一行特殊处理
            } else if (i > 0 && j > 0) {
                dp[j] += dp[j-1]; // ↘️状态转移核心
            }
        }
    }
    return dp[n-1];
}

深度解析：

初始化陷阱
- 起点即障碍：obstacleGrid[0][0] == 1 时直接返回0
- 首行处理：当 i==0时只能从左侧继承路径数（无法从上方来）
滚动更新原理
- 空间压缩：利用 dp[j] += dp[j-1]实现二维到一维的转化
- 更新顺序：必须从左到右遍历，保证 dp[j-1]是当前行已更新的值
复杂度对比

方案时间复杂度空间复杂度优势场景
基础二维DP O(mn) O(mn) 调试直观
滚动数组 O(mn) O(n) 大数据量优化

方案	时间复杂度	空间复杂度	优势场景
基础二维DP	O(mn)	O(mn)	调试直观
滚动数组	O(mn)	O(n)	大数据量优化

案例2：TSP问题（847. 访问所有节点的最短路径）

分步代码解析：

public int shortestPathLength(int[][] graph) {
    int n = graph.length;
    int[][] dp = new int[1<<n][n];
    Queue<int[]> queue = new LinkedList<>();
  
    // 🎯初始化所有起点
    for (int i=0; i<n; i++) {
        Arrays.fill(dp[1<<i][i], n*n); // 初始化为极大值
        dp[1<<i][i] = 0;
        queue.offer(new int[]{1<<i, i});
    }

    // 🔁 BFS状态转移
    while (!queue.isEmpty()) {
        int[] state = queue.poll();
        int mask = state[0], u = state[1];
  
        for (int v : graph[u]) {
            int newMask = mask | (1 << v);
            if (dp[newMask][v] > dp[mask][u] + 1) {
                dp[newMask][v] = dp[mask][u] + 1;
                queue.offer(new int[]{newMask, v});
            }
        }
    }
  
    // 🏁获取最终结果
    int res = Integer.MAX_VALUE;
    for (int x : dp[(1<<n)-1]) {
        res = Math.min(res, x);
    }
    return res;
}

四层递进解析：

状态设计精要
- mask二进制位表示访问过的节点，如 101表示节点0和2已访问
- dp[mask][u]：当前访问状态为 mask且位于节点 u时的最短路径
BFS与DP的融合
算法特性分析
- 时间复杂度：O(n²·2ⁿ) → 适合n≤12的中等规模问题
- 空间优化：使用优先队列替代完整DP表可提升效率

五、💡 思维拓展训练

💬 进阶思考

🤔 当编辑距离问题中的操作代价不同时（如插入代价2，删除代价1），如何改造状态转移方程？欢迎在评论区留下你的解法！

🎁 小彩蛋：在力扣题库搜索「状态压缩」标签，探索更多精彩题目！

💡 思路参考

编辑距离变形题：若允许交换相邻字符操作（代价为1），如何改造状态方程？

// 新增交换操作判断
if (i>=2 && j>=2 && 
    word1.charAt(i-1)==word2.charAt(j-2) && 
    word1.charAt(i-2)==word2.charAt(j-1)) {
    dp[i][j] = Math.min(dp[i][j], dp[i-2][j-2] + 1);
}