动态规划三题：从一维到二维，递推 / 记忆化 / 空间优化

三道题一脉相承一维选/不选→ 二维两串对齐→ 二维三种操作取 min。每题都给三种实现递推自底向上、记忆化递归自顶向下、空间优化。写在前面DP 四步心法不管哪道题都按这四步走绝不乱状态dp[...]表示什么转移dp[当前] ???盯住最后一步从哪来边界最小情况是几顺序保证依赖先算好一、打家劫舍一维 · 入门题目一排房子第i间有金额nums[i]相邻两间不能同时偷。求最大金额。nums [2, 7, 9, 3, 1]→ 答案12偷第 0、2、4 间291。思路盯住最后一步第i间要么偷、要么不偷。偷ii-1不能偷 →dp[i-2] nums[i]不偷i沿用dp[i-1]取较大者步答案状态dp[i] 前 i 间房能偷到的最大金额转移dp[i] max(dp[i-1], dp[i-2] nums[i])边界dp[0]nums[0],dp[1]max(nums[0], nums[1])填表nums[2,7,9,3,1]i 0 1 2 3 4 nums 2 7 9 3 1 不偷 - 2 7 11 11 偷 - - 11 10 12 dp 2 7 11 11 12 ← 答案dp 递推defrob_dp(nums):ifnotnums:return0iflen(nums)1:returnnums[0]dp[0]*len(nums)dp[0],dp[1]nums[0],max(nums[0],nums[1])foriinrange(2,len(nums)):dp[i]max(dp[i-1],dp[i-2]nums[i])returndp[-1]记忆化递归fromfunctoolsimportlru_cachedefrob_memo(nums):ifnotnums:return0lru_cache(maxsizeNone)defdfs(i):ifi0:returnnums[0]ifi1:returnmax(nums[0],nums[1])returnmax(dfs(i-1),dfs(i-2)nums[i])returndfs(len(nums)-1)空间优化两格滚动 O(1)dp[i]只依赖前两格用dp[0]/dp[1]两格 i%2交替即可。return max(dp)是因为打家劫舍的dp非递减两格里的大者就是末格。defrob_opt(nums):ifnotnums:return0iflen(nums)1:returnnums[0]dp[0,0]dp[0],dp[1]nums[0],max(nums[0],nums[1])foriinrange(2,len(nums)):dp[i%2]max(dp[(i-1)%2],dp[(i-2)%2]nums[i])returnmax(dp)二、最长公共子序列 LCS二维 · 中等题目给两个字符串求最长公共子序列不要求连续顺序不变。s1 abcde,s2 ace→ 答案3ace跳过 b、d。思路盯住末尾这对字符s1[i-1]与s2[j-1]相等这对匹配上dp[i][j] dp[i-1][j-1] 1不等丢s1[i-1]或丢s2[j-1]取较大max(dp[i-1][j], dp[i][j-1])步答案状态dp[i][j]s1前 i 个与s2前 j 个的 LCS 长度转移相等dp[i-1][j-1]1不等max(dp[i-1][j], dp[i][j-1])边界dp[0][*] dp[*][0] 0空串无公共部分填表abcde / ace a c e 0 0 0 0 a 0 1 1 1 b 0 1 1 1 c 0 1 2 2 d 0 1 2 2 e 0 1 2 3 ← 答案dp 递推deflcs_dp(s1,s2):m,nlen(s1),len(s2)dp[[0]*(n1)for_inrange(m1)]foriinrange(1,m1):forjinrange(1,n1):ifs1[i-1]s2[j-1]:dp[i][j]dp[i-1][j-1]1else:dp[i][j]max(dp[i-1][j],dp[i][j-1])returndp[m][n]记忆化递归deflcs_memo(s1,s2):lru_cache(maxsizeNone)defdfs(i,j):ifi0orj0:return0ifs1[i]s2[j]:returndfs(i-1,j-1)1returnmax(dfs(i-1,j),dfs(i,j-1))returndfs(len(s1)-1,len(s2)-1)空间优化两行滚动 O(n)只依赖上一行留两行用i%2交替。第 0 列留 0 当空 s2边界j从 1 起。答案在最后一行im-1写入dp[(m-1)%2]的第 n 列。deflcs_opt(s1,s2):ifnots1ornots2:return0nlen(s2)dp[[0]*(n1)for_inrange(2)]foriinrange(len(s1)):forjinrange(1,n1):ifs1[i]s2[j-1]:dp[i%2][j]dp[(i-1)%2][j-1]1else:dp[i%2][j]max(dp[i%2][j-1],dp[(i-1)%2][j])returndp[(len(s1)-1)%2][n]三、编辑距离二维 · 进阶题目把word1变成word2每次可插入 / 删除 / 替换一个字符求最少操作数。word1 horse,word2 ros→ 答案3。思路盯住末尾word1[i-1]与word2[j-1]相等不用动dp[i][j] dp[i-1][j-1]不等三种操作各对应一个更小子问题取最小删除word1[i-1]dp[i-1][j] 1i 退 1插入 消掉word2[j-1]dp[i][j-1] 1j 退 1替换dp[i-1][j-1] 1i、j 各退 1步答案状态dp[i][j]word1前 i 个变成word2前 j 个的最少操作数转移相等dp[i-1][j-1]不等1 min(删 dp[i-1][j], 插 dp[i][j-1], 改 dp[i-1][j-1])边界dp[i][0] i删 i 个、dp[0][j] j增 j 个记忆要点看下标往哪退——只 i 退→删只 j 退→插都退→改。在表里就是上删、左插、左上改。填表horse / ros r o s 0 1 2 3 h 1 1 2 3 o 2 2 1 2 r 3 2 2 2 s 4 3 3 2 e 5 4 4 3 ← 答案dp 递推defedit_dp(word1,word2):n,mlen(word1),len(word2)dp[[0]*(m1)for_inrange(n1)]foriinrange(n1):dp[i][0]i# 删 i 个forjinrange(m1):dp[0][j]j# 增 j 个foriinrange(1,n1):forjinrange(1,m1):ifword1[i-1]word2[j-1]:dp[i][j]dp[i-1][j-1]else:dp[i][j]1min(dp[i-1][j],# 删dp[i][j-1],# 插dp[i-1][j-1])# 改returndp[n][m]记忆化递归defedit_memo(word1,word2):lru_cache(maxsizeNone)defdfs(i,j):ifi0:returnj# 插 j 个ifj0:returni# 删 i 个ifword1[i-1]word2[j-1]:returndfs(i-1,j-1)return1min(dfs(i-1,j),# 删dfs(i,j-1),# 插dfs(i-1,j-1))# 改returndfs(len(word1),len(word2))空间优化两行滚动 O(n)两个要点都是踩坑高发区defedit_opt(word1,word2):n,mlen(word1),len(word2)dp[[0]*(m1)for_inrange(2)]forjinrange(m1):dp[0][j]jforiinrange(1,n1):dp[i%2][0]i# ★每行开头必须更新第 0 列forjinrange(1,m1):ifword1[i-1]word2[j-1]:dp[i%2][j]dp[(i-1)%2][j-1]else:dp[i%2][j]1min(dp[(i-1)%2][j],# 删dp[i%2][j-1],# 插dp[(i-1)%2][j-1])# 改returndp[n%2][m]# ★取最终行第 m 列不是 min(整行)总结对照题维度状态转移核心求时间空间(优化)打家劫舍一维dp[i]前i房最大金额max(dp[i-1], dp[i-2]nums[i])最大O(n)O(1)LCS二维dp[i][j]两前缀的 LCS 长相等1不等max(上,左)最大O(mn)O(n)编辑距离二维dp[i][j]i→j 最少操作相等0不等1min(上,左,左上)最小O(mn)O(n)递进规律一维→二维max→min“选/不选两路→三种操作三路”。把每题的最后一步想清楚三种实现就是同一套思路的三种写法。系列学习见附件