二维 DP 的空间优化
只保留 DP 表的当前行和上一行，将 LCS 与编辑距离的空间复杂度从 O(mn) 降至 O(min(m,n))。
二维 DP 的空间优化 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
二维 DP 中空间为何重要
对于长度为 1000 的字符串，二维 DP 表需要 1000×1000 = 1,000,000 个单元格——对于 64 位整数，大约需要 8 MB。对于更长的序列（DNA 比对、大型文本差异比较），这会变得不切实际。关键观察是，大多数二维 DP 递推关系只会查看当前行和上一行，因此可以将整个表压缩为一个或两个一维数组。这就是二维 DP 空间优化的核心。
# Full 2D DP: O(mn) space
# LCS for 1000-char strings
m, n = 1000, 1000
dp_2d_size = m * n * 8 # bytes (64-bit ints)
print(f'2D table: {dp_2d_size:,} bytes = {dp_2d_size//1024} KB')
# 1D rolling array: O(n) space
dp_1d_size = n * 8
print(f'1D array: {dp_1d_size:,} bytes = {dp_1d_size} bytes')
print(f'Space saving: {dp_2d_size // dp_1d_size}x')滚动数组模式
滚动数组模式用表示上一行的一维数组替代完整的二维表。计算第 i 行时，使用当前值 dp[j]（其中仍保存上一行的 dp[i-1][j]）以及刚刚更新的 dp[j-1]（即 dp[i][j-1]）来更新每个单元格。diagonal 变量会在 dp[i-1][j-1] 被覆盖前保存它。此模式适用于 LCS、编辑距离以及大多数二维 DP 问题。
# Rolling array template for 2D DP
# Before update: dp[j] holds dp[i-1][j] (previous row)
# After update: dp[j] holds dp[i][j] (current row)
def rolling_array_template(grid):
m, n = len(grid), len(grid[0])
dp = [0] * (n + 1) # represents one row
for i in range(1, m + 1):
diag = 0 # stores dp[i-1][j-1] before overwrite
for j in range(1, n + 1):
temp = dp[j] # save dp[i-1][j] before overwriting
# compute dp[i][j] using dp[j] (above) and dp[j-1] (left) and diag
dp[j] = diag + dp[j] + dp[j-1] # placeholder logic
diag = temp
return dp[n]使用 O(min m,n) 空间的 LCS
对于 LCS，请确保 text1 是较短的字符串（这样 n 较小）。分配大小为 n+1 的一维数组。逐行处理。在每个单元格处：保存 temp = dp[j]（即 dp[i-1][j]）。然后：如果字符匹配，dp[j] = diag + 1；否则 dp[j] = max(dp[j], dp[j-1])。最后设置 diag = temp。处理完所有行后，dp[n] 保存 LCS 的长度。
def lcs_space_opt(text1, text2):
# Ensure text2 is the shorter one
if len(text1) < len(text2):
text1, text2 = text2, text1
m, n = len(text1), len(text2)
dp = [0] * (n + 1)
for i in range(1, m + 1):
diag = 0
for j in range(1, n + 1):
temp = dp[j] # dp[i-1][j]
if text1[i-1] == text2[j-1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp
return dp[n]
print(lcs_space_opt('ABCBDAB', 'BDCABA')) # 4
print(lcs_space_opt('AGGTAB', 'GXTXAYB')) # 4使用 O(n) 空间的编辑距离
编辑距离使用相同的滚动模式。初始一维数组表示第 0 行：dp[j] = j（插入 j 个字符）。对于每一行 i，设置 dp[0] = i（删除 i 个字符），并在更新前保存 diag = dp[0]。在内部循环中，保存 temp = dp[j]，根据插入（dp[j-1]+1）、删除（dp[j]+1）和替换（diag + cost）计算新值，然后设置 diag = temp。
def edit_dist_opt(s, t):
m, n = len(s), len(t)
dp = list(range(n + 1)) # row 0: dp[0][j] = j
for i in range(1, m + 1):
diag = dp[0] # dp[i-1][0] before dp[0] update
dp[0] = i # dp[i][0] = i
for j in range(1, n + 1):
temp = dp[j] # dp[i-1][j]
cost = 0 if s[i-1] == t[j-1] else 1
dp[j] = min(
dp[j-1] + 1, # insert
dp[j] + 1, # delete
diag + cost # replace or match
)
diag = temp
return dp[n]
print(edit_dist_opt('horse', 'ros')) # 3
print(edit_dist_opt('intention', 'execution')) # 5使用 O(n) 空间的最小路径和
对于网格上的最小路径和问题，一维滚动数组初始为第一行的前缀和（第一行中的每个单元格都只有一种到达方式）。对于后续每一行，从左到右更新：dp[j] 更新前是上方一行的值（dp[i-1][j]），而刚刚更新的左侧 dp[j-1] 来自左边。这里不需要对角元素，因为最小路径和不需要使用对角单元格。
def min_path_sum_opt(grid):
m, n = len(grid), len(grid[0])
dp = [float('inf')] * n
dp[0] = 0
for i in range(m):
# Update first column (only from above)
dp[0] += grid[i][0]
for j in range(1, n):
# min of above (dp[j] = old) and left (dp[j-1] = updated)
dp[j] = grid[i][j] + min(dp[j], dp[j-1])
return dp[n-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_opt(grid)) # 7需要访问对角元素时
不是所有二维 DP 问题都能用简单的滚动数组压缩，因为有些问题在对角元素 dp[i-1][j-1] 被覆盖后仍需要它。解决方法始终相同：在更新 dp[j] 之前保存 temp = dp[j]，并在计算下一列时将其用作 diag。这个单格前瞻可以清晰地处理所有三方向递推关系（LCS、编辑距离）。
# Recap: the diagonal save pattern
# Without it: dp[j-1] updated (left) and dp[j] about to be overwritten
# With it:
def show_diagonal_pattern(s1, s2):
n = len(s2)
dp = [0] * (n + 1)
for ch1 in s1:
diag = 0 # was dp[i-1][0] = 0 for LCS
for j, ch2 in enumerate(s2, 1):
temp = dp[j] # SAVE before overwrite
if ch1 == ch2:
dp[j] = diag + 1 # use saved diagonal
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp # advance diagonal
return dp[n]
print(show_diagonal_pattern('ABCBDAB', 'BDCABA')) # 4二维背包的空间优化
0/1 背包问题同样受益于空间优化。完整的二维表维度为（物品数+1）×（容量+1）。滚动数组将其降低到 O(容量)。与 LCS/编辑距离的关键区别在于：按逆序遍历容量维度（从高到低）。这样可确保每件物品最多被计入一次——正序遍历会允许同一件物品被选择多次。
def knapsack_01(weights, values, capacity):
dp = [0] * (capacity + 1)
for w, v in zip(weights, values):
# Reverse order: prevents using the same item twice
for c in range(capacity, w - 1, -1):
dp[c] = max(dp[c], dp[c - w] + v)
return dp[capacity]
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
cap = 7
print(knapsack_01(weights, values, cap)) # 9 (items 3+4: weight 3+4=7, value 4+5=9)正序与逆序遍历
了解内层循环应以哪个方向遍历至关重要：0/1 背包使用逆序（每件物品最多使用一次——回看之前的状态可以避免重复使用）；无界背包使用正序（查看已经更新的状态可以允许多次使用同一件物品）。方向选择错误会在不易察觉的情况下将 0/1 背包变成无界背包，反之亦然。选择方向前，请务必确认约束条件。
# 0/1 Knapsack: each item used AT MOST ONCE → iterate reverse
def knapsack_01_demo(weights, values, cap):
dp = [0] * (cap + 1)
for w, v in zip(weights, values):
for c in range(cap, w-1, -1): # REVERSE
dp[c] = max(dp[c], dp[c-w] + v)
return dp[cap]
# Unbounded Knapsack: items can be reused → iterate forward
def knapsack_unbounded(weights, values, cap):
dp = [0] * (cap + 1)
for c in range(1, cap + 1):
for w, v in zip(weights, values):
if c >= w:
dp[c] = max(dp[c], dp[c-w] + v) # FORWARD
return dp[cap]
print(knapsack_01_demo([2,3],[3,4],5)) # 7
print(knapsack_unbounded([2,3],[3,4],5)) # 8 (use weight-2 twice: 3+3=6? or 4+... )使用 O(n) 空间的不同路径
对于不同路径问题，整个表可以由单行替代。将所有单元格初始化为 1（第一行）。对于后续每一行，从左到右更新：dp[j] += dp[j-1]。这里不需要对角元素，因为递推关系只使用上方单元格（dp[j]，更新前的当前值）和左侧单元格（dp[j-1]，已经更新）。这是最简单的二维到一维压缩。
def unique_paths_opt(m, n):
dp = [1] * n # first row: all 1s
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1] # above (dp[j]) + left (dp[j-1])
return dp[n-1]
# With obstacles
def unique_paths_obstacles_opt(grid):
m, n = len(grid), len(grid[0])
dp = [0] * n
dp[0] = 1
for i in range(m):
if grid[i][0] == 1: dp[0] = 0 # blocked column
for j in range(1, n):
if grid[i][j] == 1: dp[j] = 0 # blocked
else: dp[j] += dp[j-1]
return dp[n-1]
print(unique_paths_opt(3, 7)) # 28
print(unique_paths_obstacles_opt([[0,0,0],[0,1,0],[0,0,0]])) # 2复杂递推关系的双行缓冲区
当递推关系需要使用前两行或更多行中的单元格时（例如某些区间 DP 变体或三维 DP 降维），可以使用双行缓冲区：维护 prev 和 curr 数组，并在每行处理完后交换它们。这样可使用 O(2n) = O(n) 的空间。对于需要回看前 k 行的递推关系，可以使用循环缓冲区维护 k 个数组。这是单行滚动数组模式的推广。
def lcs_two_row_buffer(s1, s2):
m, n = len(s1), len(s2)
prev = [0] * (n + 1) # dp[i-1]
curr = [0] * (n + 1) # dp[i]
for i in range(1, m + 1):
curr[0] = 0
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev, curr = curr, prev # swap (curr becomes prev)
return prev[n] # after swap, prev holds the last computed row
print(lcs_two_row_buffer('ABCBDAB', 'BDCABA')) # 4无法进行空间优化时
空间优化并非总是可行。如果需要重建最优解（而不仅仅是它的值），通常需要保留完整的表以进行回溯。可行的替代方案包括：(1) 存储一个大小相同的独立决策表。(2) 使用Hirschberg 算法，通过递归地在中点划分问题，在 O(mn) 时间和 O(min(m,n)) 空间内计算 LCS 并完成重建。(3) 在需要重建时接受 O(mn) 的空间复杂度。
# When reconstruction needed: must keep full table or use Hirschberg
# Hirschberg's idea: compute LCS length in O(n) space at midpoint of s1,
# recurse on left and right halves. O(mn) time, O(n) space + reconstruction.
# For interview: mention the trade-off
# 'I can reduce to O(n) space if only the value is needed.
# To also reconstruct the sequence, I need the full O(mn) table
# or a more complex divide-and-conquer approach.'
print('Space opt: O(n) for length only')
print('Full table: O(mn) needed for reconstruction')快速检查
测试您对本课中“数据结构与算法——编码面试准备”相关概念的理解。
课程回顾
在本课中您学到了：当只需要前一行时，可以使用滚动一维数组将二维 DP 表压缩到 O(n) 空间，对角变量模式（在覆盖前保存临时值）可以处理需要上一行前一列单元格的递推关系，以及0/1 背包按逆序遍历容量，而无界背包按正序遍历。接下来我们将学习回溯模板：选择、探索、撤销选择——这是穷举搜索算法的基础。
常见问题解答
「二维 DP 的空间优化」课时是免费的吗？
是的 — 「二维 DP 的空间优化」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「二维 DP 的空间优化」这节课中我会学到什么？
只保留 DP 表的当前行和上一行，将 LCS 与编辑距离的空间复杂度从 O(mn) 降至 O(min(m,n))。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「二维 DP 的空间优化」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 网格中的不同路径与最小路径和
- 最长公共子序列
- 编辑距离（Levenshtein）
- 二维 DP 的空间优化