原文地址：https://www.cnblogs.com/ryuo-ou/p/19834294 同步说明：该文已完整同步到站内博客，便于统一检索和阅读。
在动态规划（DP）题库中，二维网格、二维字符串编辑距离等问题常常是 DP 新手跨不过去的门槛。当你终于写出了长篇大论的 dp[i][j] 状态转移方程通过了所有测试用例时，可能还没来得及开心，面试官就会微笑着问一句：“代码不错，在这个题目场景下你的申请了 \(O(M \times N)\) 大小的 dp 矩阵，如果数据规模极大，容易出现内存溢出（OOM）。能把空间复杂度优化到 \(O(N)\) 吗？ ”
这篇文章，我们将围绕 LeetCode 面试高频题 不同路径 II（LC 63） 的 Go 语言实现，一探究竟：到底怎么把二维 DP 降维成一维 DP？
一、 二维 DP 怎么解？（朴素思路）
所谓二维 DP，最典型的状态定义是一张网状大表：dp[i][j] 代表“某种东西走到第 \(i\) 行、第 \(j\) 列时的结果/方案数”。对于矩阵求路径的问题而言（机器人只能向下或向右），规律永远是直白的：
也就是：
遇到障碍物怎么办？
如果地图网格 obstacleGrid[i][j] 是个障碍物（值为 \(1\)），那这格连落脚都不行，直接硬性规定 dp[i][j] = 0。
在此思路下，哪怕是一个刚刚懂了双层 for 循环的人，也能够很轻易地初始化一个 \(M \times N\) 的二维数组然后一排排推下去解题。但这太费内存了。
二、 空间优化的灵魂思路：“滚动数组”
请注意观察最核心的转移方程：
你敏锐地发现：为了计算出第 \(i\) 行的所有结果，我们唯一需要的历史数据，就只有刚刚算好的第 \(i-1\) 行的数据。 更早之前算过的（\(i-2\), \(i-3\) 等等行），对于接下来的推导来说，已经是毫无价值的数字垃圾了。
既然只要保留上一排，那我们为什么要斥巨资开辟一座 \(M\) 层的大楼？
只需要一层长度为 \(N\) 的一维数组 dp 足矣。
如何压榨一维数组实现“魔法降维”？
假设我们当前一维数组里正原封不动保留着上一排（老 \(i-1\) 行）所有列的答案，数组长这样 [旧dp0, 旧dp1, 旧dp2, ... 旧dpN]。
我们要去求解最新这一排（第 \(i\) 行）时，依然是从左向右挨个求。针对最新的格子求解时：
- 等号右边的
旧的 dp[j]还没被覆盖，所以拿到的它原本正是上方一格传递下来的路径数！ - 等号右边的
新的 dp[j-1]，因为我们每一排总是从左向右推算的，在此刻推算 \(j\) 时，\(j-1\) 那个格子的值早在这个循环周期的前一秒被刷新出炉了！这就等价于刚刚从左边传过来的路径树。
如此一来一回，我们在一边向右推进的过程中，顺势覆盖掉数组里的老数据，完美地“边读边涂”，极度克制地用 \(O(N)\) 的一条线度过了 \(M \times N\) 的沧海桑田。
三、 Go 语言核心优化代码实战
以下就是经过了降维打击之后的极简代码，这往往也是面试官最终想要看到的答卷：
package main // uniquePathsWithObstacles 空间复杂度 O(n) 一维 DP 优化解法
func uniquePathsWithObstacles(obstacleGrid [][]int) int { m, n := len(obstacleGrid), len(obstacleGrid[0]) if obstacleGrid[0][0] == 1 { return 0 // 开门撞南墙直接寄 } dp := make([]int, n) dp[0] = 1 for i := 0; i < m; i++ { for j := 0; j < n; j++ { if obstacleGrid[i][j] == 1 { // 遇到石头，此路不通。更新此处“新 dp[j]”为 0 dp[j] = 0 } else if j > 0 { // 等号右侧： // dp[j] 是上一轮留在这个坑的数据 -> 上方来的路线 // dp[j-1] 是本轮中上一步刚更新的数据 -> 左方来的路线 dp[j] = dp[j] + dp[j-1] } } } // 推完了所有行，最末尾的数据即为抵达终点的路径总数 return dp[n-1]
}
四、 结语
在动态规划的进阶之路上，空间优化（滚动数组）是必经的一张终点卷。
任何时候你发现下一个周期的推演只依赖于最近的有限几个上一个周期的状态时（比如斐波那契数列的迭代、0-1 背包的一维拍平、网格路径等），请一定要养成“降维打击”的思维惯性，删掉那堆积如山的二维表。你会拥抱更高性能、更优雅的基础架构。