很多刚学动态规划的开发者，写完DP代码后，会发现最后生成的状态数组占了大量内存——比如要算第10000个斐波那契数，普通写法得开一个长度10001的数组，其实大部分空间根本用不上。这时候空间优化的技巧就派上用场了，它不是什么高深的算法魔法，只是帮你把“多余的笔记”扔掉，只留当前需要的内容，让代码更省内存、跑得更快。
一、为什么动态规划需要优化空间
1.1 先明白：动态规划其实存了很多“没用的笔记”
举个例子，算爬楼梯的问题：要到第n级台阶，只能从第n-1或n-2级上来，那第n级的方法数就是前两个的和。如果用普通DP，会开一个dp数组，从dp[0]到dp[n]都存下来，但是算到第n级的时候，dp[0]到dp[n-3]这些数，后面再也用不到了，等于白占了内存。
1.2 空间优化能解决什么实际问题
不是所有情况都需要优化，但如果是在内存很小的设备上（比如智能手表、嵌入式设备），或者算的是非常大的n（比如n=1e6，普通数组占的内存会到几MB甚至几十MB），优化后能节省大量资源，让代码跑起来更流畅。
二、滚动数组：只留“最近几页笔记”的技巧
2.1 滚动数组的核心：只存当前需要的状态
还是用爬楼梯的例子，刚才说只需要前两个数，那我们不用整个数组，只用两个变量，a和b分别存n-2和n-1的结果，每次算新的数，就把a和b往后移，新的数是a+b，这样每次只存两个数，不管n多大，内存都不变。 示例代码如下：
# 技术栈：Python
# 滚动数组实现斐波那契数列（第n项）
def fib_rolling(n):
if n <= 1:
return n
# 初始化：a是n-2项的结果，b是n-1项的结果，对应初始的第0和第1项
a, b = 0, 1
# 从第2项开始循环，直到计算到第n项
for _ in range(2, n + 1):
# 新项等于前两项之和，然后更新a和b，让它们始终对应最新的两个状态
a, b = b, a + b
return b
# 测试：第10项斐波那契数为55，输出结果应为55
print(fib_rolling(10))
对比普通DP写法，你会发现滚动数组用的空间是固定的，而普通写法的空间随n增长，当n达到1e6时，普通写法需要约8MB的内存（每个int占4字节），滚动数组只需要8字节，差距非常明显。
2.2 滚动数组的适用场景
只要动态规划的转移，只依赖前面固定数量的状态，比如只依赖前1个（如“最大子数组和”）、前2个（如斐波那契）或前3个状态，都可以用滚动数组。类似的经典问题还有“青蛙跳台阶”“打家劫舍”，都是非常适合用滚动数组优化的场景。
2.3 滚动数组的优缺点
优点是空间复杂度直接降到O(1)，非常节省内存，代码逻辑直观易懂，只要对应好变量的更新顺序就行；缺点是如果依赖的状态数量多（比如需要前5个状态），需要的变量会变多，可读性略有下降，不过日常开发中转移依赖一般不会超过3个，这个缺点基本可以忽略。
三、原地更新：在原来的数组上“改出结果”
3.1 原地更新的核心：不额外开新空间，直接修改原数组
原地更新是一维动态规划常用的优化技巧，最经典的例子就是01背包问题。普通的01背包会用二维数组dp[i][w]表示前i个物品、容量w的最大价值，这个二维数组其实可以简化成一维，并且直接在原一维数组上原地修改，不需要额外的存储空间。 示例代码如下：
# 技术栈：Python
# 01背包问题，空间优化为一维原地更新
def knapsack_01(weights, values, capacity):
n = len(weights)
# 一维数组dp[w]表示容量为w时能装的最大价值，初始全为0（容量0时价值为0）
dp = [0] * (capacity + 1)
# 遍历每个物品，逐个更新容量
for i in range(n):
# 重点：必须逆序遍历容量！正序会导致重复计算同一个物品，变成完全背包问题
for w in range(capacity, weights[i] - 1, -1):
# 原地更新：取“不拿当前物品的原有价值”和“拿当前物品的价值”的最大值
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
# 测试：物品重量为[2,3,4]，价值为[3,4,5]，容量为5，最大价值为3+4=7，输出结果应为7
print(knapsack_01([2,3,4], [3,4,5],5))
这里把原来的二维空间O(n*w)，降到了一维的O(w)，当物品数量多、容量大时，节省的空间非常可观。
3.2 原地更新的关键：遍历顺序不能乱
刚才的01背包里，为什么容量要逆序遍历？因为如果正序遍历，当计算容量w时，dp[w-weights[i]]已经被当前物品的更新覆盖过，相当于重复拿了同一个物品，这就变成了允许重复拿的完全背包问题，和我们要的01背包逻辑不符，所以逆序是原地更新的核心注意点，也是容易踩坑的地方。
3.3 适用场景
原地更新只适合一维的动态规划问题，尤其是状态只依赖同一层的其他状态，不需要跨层的旧状态，比如01背包、一维的路径计数、最大子数组问题等，只要符合这个条件，都可以尝试原地更新优化。
四、降维打击：从高维状态压成低维
4.1 高维DP的冗余来源
很多动态规划问题会用到二维甚至更高维的状态，比如最长公共子序列（LCS），普通的二维DP定义是dp[i][j]表示第一个字符串前i个字符、第二个字符串前j个字符的最长公共子序列长度。但这个二维数组里，很多空间其实是重复的——计算dp[i][j]时，只需要用到上一行的dp[i-1][j]、当前行前一列的dp[i][j-1]，以及上一行前一列的dp[i-1][j-1]，不需要更早的行，所以可以把二维压缩成一维。 示例代码如下：
# 技术栈：Python
# 最长公共子序列，二维DP降维到一维优化
def lcs_optimized(s1, s2):
m, n = len(s1), len(s2)
# 用一维数组存储状态，长度为短字符串的长度+1，节省空间
dp = [0] * (n + 1)
# 遍历第一个字符串的每个字符
for i in range(1, m + 1):
# prev变量保存上一行前一列的状态，也就是dp[i-1][j-1]，会被后续更新覆盖，需要单独存
prev = 0
# 遍历第二个字符串的每个字符
for j in range(1, n + 1):
# temp保存当前dp[j]的值，用于更新prev
temp = dp[j]
# 两个字符相等，长度加1，等于prev（上一行前一列）+1
if s1[i-1] == s2[j-1]:
dp[j] = prev + 1
else:
# 字符不等，取上一行当前列和当前行前一列的最大值
dp[j] = max(dp[j], dp[j-1])
# 更新prev为当前的temp，作为下一个j的上一行前一列状态
prev = temp
return dp[n]
# 测试：s1="abcde"，s2="ace"，最长公共子序列是"ace"，长度为3，输出结果应为3
print(lcs_optimized("abcde", "ace"))
这里把原来的二维空间O(m*n)，降到了O(min(m,n))，如果其中一个字符串是1e5的长度，降维后的空间只有1e5，而原来的二维空间需要1e10，根本无法存储，降维打击的效果非常明显。
4.2 降维的判断依据
只要动态规划的转移方程，不需要依赖早于前1个维度的状态，就可以进行降维。比如二维DP里只需要上一行的状态，不需要上上行，就可以降成一维；如果是三维DP只需要上一层的状态，就可以降到二维。
4.3 适用场景
降维打击适合所有高维动态规划问题，尤其是二维DP，比如编辑距离问题、矩阵路径和问题、不同路径问题，这些问题的转移都只依赖前1个维度的状态，非常适合用降维优化空间。
五、这些优化的实际场景和避坑要点
5.1 常见的应用场景
这些空间优化技巧不是只为了应付算法面试题，实际开发中也非常有用：比如移动端开发处理大数据量的列表时，减少内存占用能避免APP卡顿或崩溃；嵌入式设备的内存非常有限，哪怕几百字节的优化都能让程序正常运行；后端高并发场景下，优化内存能让服务器承载更多请求，提高系统的稳定性。
5.2 三种优化的优缺点对比
滚动数组的优点是O(1)空间，逻辑清晰，适合依赖状态少的场景；缺点是只有转移依赖状态数量少的时候才好用，依赖多的话变量会变多。原地更新的优点是O(1)空间，一维场景下代码简洁；缺点是容易踩遍历顺序的坑，只适合一维DP。降维打击的优点是把高维空间大幅压缩，适合复杂的高维DP；缺点是代码复杂度高，处理临时状态时容易出错。
5.3 必须注意的避坑点
第一，一定要先写对普通的动态规划代码，再改优化版本，不然很容易在优化时出错，因为状态存储的方式改变了，转移逻辑容易混淆；第二，原地更新的遍历顺序绝对不能乱，比如01背包的逆序遍历，正序会导致逻辑错误；第三，降维时要注意保存被覆盖的临时状态，比如LCS里的prev变量，用来保存上一行前一列的值；第四，不要过度优化，如果问题本身的规模很小（比如n=10），直接用普通数组就好，硬优化会降低代码的可读性，得不偿失。
六、总结
动态规划的空间优化，本质上是按需分配内存，把原来存的所有状态换成只存当前计算需要的最少内容，不是什么高端算法，只是换个思路管理数据而已。滚动数组是留最近的必要状态，原地更新是在原有数组上修改，降维打击是把高维的状态压成低维的薄片，三种技巧各有各的适用场景。开发时要根据问题的规模、内存限制选择合适的优化方式，先保证代码的正确性和可读性，再考虑性能优化，毕竟能维护的代码才是有价值的代码。
Comments