1. 动态规划与递归的本质差异第一次真正理解动态规划与递归的区别是在解决LeetCode第70题爬楼梯问题时。当时我用递归写出了优雅的解法提交后却遇到了超时错误——这让我意识到看似相似的两种方法在性能上竟有如此巨大的鸿沟。递归本质上是一种自顶向下的问题解决方式。就像俄罗斯套娃我们把大问题不断拆解成更小的同类问题直到遇到基线条件。以斐波那契数列为例fib(n) fib(n-1) fib(n-2)的数学定义可以直接翻译成递归代码def fib(n): if n 1: return n return fib(n-1) fib(n-2)但这种朴素递归存在致命缺陷——重复计算。计算fib(5)时需要计算fib(3)两次fib(2)三次时间复杂度呈指数级增长(O(2^n))。我在本地测试时计算fib(40)竟然需要近30秒动态规划则采用自底向上的策略像搭积木一样从基础情况逐步构建解决方案。它通过存储子问题的解记忆化来避免重复计算def fib_dp(n): if n 1: return n dp [0]*(n1) dp[1] 1 for i in range(2, n1): dp[i] dp[i-1] dp[i-2] return dp[n]这个版本的时间复杂度是线性的(O(n))计算fib(40)几乎瞬间完成。空间复杂度还可以进一步优化到O(1)因为当前状态只依赖前两个状态def fib_dp_optimized(n): if n 1: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b关键洞察动态规划的核心在于状态转移方程和重叠子问题。当问题可以分解为相互依赖的子问题且这些子问题会被重复计算时就是使用DP的黄金时机。2. 从递归到动态规划的思维转换很多动态规划问题最初都可以用递归思路解决。以经典的01背包问题为例假设背包容量W10物品列表为[(2,6),(2,3),(6,5),(5,4),(4,6)]重量,价值。2.1 递归解法分析递归思路非常直观对每个物品我们有两种选择——放入或不放入背包。我们需要尝试所有可能性并找出最大价值def knapsack_recursive(W, wt, val, n): if n 0 or W 0: return 0 if wt[n-1] W: return knapsack_recursive(W, wt, val, n-1) else: return max( val[n-1] knapsack_recursive(W-wt[n-1], wt, val, n-1), knapsack_recursive(W, wt, val, n-1) )这个解法虽然正确但时间复杂度是O(2^n)。当物品数量超过30时计算就变得不可行。2.2 动态规划优化我们引入DP表格来存储中间结果。dp[i][w]表示考虑前i个物品在背包容量为w时能获得的最大价值def knapsack_dp(W, wt, val, n): dp [[0]*(W1) for _ in range(n1)] for i in range(1, n1): for w in range(1, W1): if wt[i-1] w: dp[i][w] max(val[i-1] dp[i-1][w-wt[i-1]], dp[i-1][w]) else: dp[i][w] dp[i-1][w] return dp[n][W]这个解法的时间复杂度降为O(nW)空间复杂度也是O(nW)。通过观察状态转移方程可以发现当前行只依赖上一行因此空间可以优化到O(W)def knapsack_dp_optimized(W, wt, val, n): dp [0]*(W1) for i in range(1, n1): for w in range(W, wt[i-1]-1, -1): dp[w] max(val[i-1] dp[w - wt[i-1]], dp[w]) return dp[W]实战技巧在解决DP问题时先写出递归解法然后分析重复计算的子问题最后构建DP表格。这种方法尤其适合DP初学者。3. 动态规划的经典问题解析3.1 最长公共子序列(LCS)给定两个字符串ABCBDAB和BDCABA它们的最长公共子序列是BCBA。LCS问题是理解二维DP的绝佳案例。状态转移方程如果text1[i-1] text2[j-1]则dp[i][j] dp[i-1][j-1] 1否则dp[i][j] max(dp[i-1][j], dp[i][j-1])def longestCommonSubsequence(text1, text2): m, n len(text1), len(text2) dp [[0]*(n1) for _ in range(m1)] for i in range(1, m1): for j in range(1, n1): if text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1]) return dp[m][n]3.2 编辑距离计算将word1转换为word2所需的最少操作次数插入、删除或替换字符。例如horse到ros的编辑距离是3。状态转移方程如果word1[i-1] word2[j-1]则dp[i][j] dp[i-1][j-1]否则dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n]3.3 股票买卖问题LeetCode第121题只允许完成一笔交易时的最大利润。例如[7,1,5,3,6,4]的最大利润是5第二天买入第五天卖出。状态定义min_price至今为止的最低价格max_profit至今为止的最大利润def maxProfit(prices): min_price float(inf) max_profit 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit对于允许完成k笔交易的一般情况状态转移会变得更复杂需要三维DP数组来记录天数、交易次数和持有状态。4. 递归的高级应用场景4.1 树的遍历二叉树的前序遍历递归版本极其简洁def preorderTraversal(root): result [] def traverse(node): if not node: return result.append(node.val) traverse(node.left) traverse(node.right) traverse(root) return result虽然递归解法简洁但在处理深度很大的树时可能引发栈溢出。这时可以用显式栈实现迭代版本def preorderTraversal_iterative(root): if not root: return [] stack, result [root], [] while stack: node stack.pop() result.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result4.2 排列组合问题生成n对括号的所有合法组合。例如n3时输出为[((())),(()()),(())(),()(()),()()()]。递归解法通过跟踪开闭括号数量来保证合法性def generateParenthesis(n): def backtrack(current, open_count, close_count): if len(current) 2*n: result.append(current) return if open_count n: backtrack(current(, open_count1, close_count) if close_count open_count: backtrack(current), open_count, close_count1) result [] backtrack(, 0, 0) return result4.3 递归目录遍历在文件系统操作中递归遍历目录是最自然的实现方式伪代码def traverse_directory(path): for entry in os.listdir(path): full_path os.path.join(path, entry) if os.path.isdir(full_path): traverse_directory(full_path) # 递归调用 else: process_file(full_path)需要注意的是实际应用中应该添加对符号链接和权限异常的处理避免无限递归或安全漏洞。5. 动态规划的优化技巧5.1 状态压缩当DP状态只依赖有限的前几个状态时可以大幅减少空间复杂度。以斐波那契数列为例我们只需要保存前两个状态def fib_optimized(n): if n 1: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b5.2 滚动数组对于二维DP问题如果当前行只依赖前一行可以使用两行数组交替更新def knapsack_rolling_array(W, wt, val, n): dp [[0]*(W1) for _ in range(2)] for i in range(1, n1): curr, prev i % 2, (i-1) % 2 for w in range(1, W1): if wt[i-1] w: dp[curr][w] max(val[i-1] dp[prev][w-wt[i-1]], dp[prev][w]) else: dp[curr][w] dp[prev][w] return dp[n % 2][W]5.3 记忆化搜索这是介于递归和DP之间的方法保留递归结构但通过缓存避免重复计算def fib_memo(n, memo{}): if n 1: return n if n not in memo: memo[n] fib_memo(n-1, memo) fib_memo(n-2, memo) return memo[n]记忆化搜索特别适合状态转移不规则或难以用迭代方式表达的问题。6. 常见错误与调试技巧6.1 递归常见陷阱栈溢出递归深度过大导致调用栈溢出。解决方法包括转换为迭代版本使用尾递归优化但Python不支持增加递归深度限制sys.setrecursionlimit()重复计算同一子问题被反复计算。解决方法添加记忆化缓存改用动态规划基线条件缺失忘记处理递归终止条件导致无限递归。6.2 DP调试技巧打印DP表格这是理解DP运行过程的最直接方式def print_dp_table(dp): for row in dp: print( .join(f{num:2} for num in row))小规模测试先用小输入测试确保基础情况正确。边界检查特别注意数组索引是否越界特别是当i0或j0时。逆向推导从最终结果回溯验证状态转移的正确性。调试心得当DP结果不符合预期时我通常会先手动计算小规模例子的正确结果然后逐步打印DP表格的中间状态找出第一个出现错误的位置这往往能快速定位问题所在。 
长河君 · 2026/11/2 16:28:03 · 阅读 1.2k 动态规划与递归：核心差异与优化技巧
1. 动态规划与递归的本质差异第一次真正理解动态规划与递归的区别是在解决LeetCode第70题爬楼梯问题时。当时我用递归写出了优雅的解法提交后却遇到了超时错误——这让我意识到看似相似的两种方法在性能上竟有如此巨大的鸿沟。递归本质上是一种自顶向下的问题解决方式。就像俄罗斯套娃我们把大问题不断拆解成更小的同类问题直到遇到基线条件。以斐波那契数列为例fib(n) fib(n-1) fib(n-2)的数学定义可以直接翻译成递归代码def fib(n): if n 1: return n return fib(n-1) fib(n-2)但这种朴素递归存在致命缺陷——重复计算。计算fib(5)时需要计算fib(3)两次fib(2)三次时间复杂度呈指数级增长(O(2^n))。我在本地测试时计算fib(40)竟然需要近30秒动态规划则采用自底向上的策略像搭积木一样从基础情况逐步构建解决方案。它通过存储子问题的解记忆化来避免重复计算def fib_dp(n): if n 1: return n dp [0]*(n1) dp[1] 1 for i in range(2, n1): dp[i] dp[i-1] dp[i-2] return dp[n]这个版本的时间复杂度是线性的(O(n))计算fib(40)几乎瞬间完成。空间复杂度还可以进一步优化到O(1)因为当前状态只依赖前两个状态def fib_dp_optimized(n): if n 1: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b关键洞察动态规划的核心在于状态转移方程和重叠子问题。当问题可以分解为相互依赖的子问题且这些子问题会被重复计算时就是使用DP的黄金时机。2. 从递归到动态规划的思维转换很多动态规划问题最初都可以用递归思路解决。以经典的01背包问题为例假设背包容量W10物品列表为[(2,6),(2,3),(6,5),(5,4),(4,6)]重量,价值。2.1 递归解法分析递归思路非常直观对每个物品我们有两种选择——放入或不放入背包。我们需要尝试所有可能性并找出最大价值def knapsack_recursive(W, wt, val, n): if n 0 or W 0: return 0 if wt[n-1] W: return knapsack_recursive(W, wt, val, n-1) else: return max( val[n-1] knapsack_recursive(W-wt[n-1], wt, val, n-1), knapsack_recursive(W, wt, val, n-1) )这个解法虽然正确但时间复杂度是O(2^n)。当物品数量超过30时计算就变得不可行。2.2 动态规划优化我们引入DP表格来存储中间结果。dp[i][w]表示考虑前i个物品在背包容量为w时能获得的最大价值def knapsack_dp(W, wt, val, n): dp [[0]*(W1) for _ in range(n1)] for i in range(1, n1): for w in range(1, W1): if wt[i-1] w: dp[i][w] max(val[i-1] dp[i-1][w-wt[i-1]], dp[i-1][w]) else: dp[i][w] dp[i-1][w] return dp[n][W]这个解法的时间复杂度降为O(nW)空间复杂度也是O(nW)。通过观察状态转移方程可以发现当前行只依赖上一行因此空间可以优化到O(W)def knapsack_dp_optimized(W, wt, val, n): dp [0]*(W1) for i in range(1, n1): for w in range(W, wt[i-1]-1, -1): dp[w] max(val[i-1] dp[w - wt[i-1]], dp[w]) return dp[W]实战技巧在解决DP问题时先写出递归解法然后分析重复计算的子问题最后构建DP表格。这种方法尤其适合DP初学者。3. 动态规划的经典问题解析3.1 最长公共子序列(LCS)给定两个字符串ABCBDAB和BDCABA它们的最长公共子序列是BCBA。LCS问题是理解二维DP的绝佳案例。状态转移方程如果text1[i-1] text2[j-1]则dp[i][j] dp[i-1][j-1] 1否则dp[i][j] max(dp[i-1][j], dp[i][j-1])def longestCommonSubsequence(text1, text2): m, n len(text1), len(text2) dp [[0]*(n1) for _ in range(m1)] for i in range(1, m1): for j in range(1, n1): if text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1]) return dp[m][n]3.2 编辑距离计算将word1转换为word2所需的最少操作次数插入、删除或替换字符。例如horse到ros的编辑距离是3。状态转移方程如果word1[i-1] word2[j-1]则dp[i][j] dp[i-1][j-1]否则dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n]3.3 股票买卖问题LeetCode第121题只允许完成一笔交易时的最大利润。例如[7,1,5,3,6,4]的最大利润是5第二天买入第五天卖出。状态定义min_price至今为止的最低价格max_profit至今为止的最大利润def maxProfit(prices): min_price float(inf) max_profit 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit对于允许完成k笔交易的一般情况状态转移会变得更复杂需要三维DP数组来记录天数、交易次数和持有状态。4. 递归的高级应用场景4.1 树的遍历二叉树的前序遍历递归版本极其简洁def preorderTraversal(root): result [] def traverse(node): if not node: return result.append(node.val) traverse(node.left) traverse(node.right) traverse(root) return result虽然递归解法简洁但在处理深度很大的树时可能引发栈溢出。这时可以用显式栈实现迭代版本def preorderTraversal_iterative(root): if not root: return [] stack, result [root], [] while stack: node stack.pop() result.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result4.2 排列组合问题生成n对括号的所有合法组合。例如n3时输出为[((())),(()()),(())(),()(()),()()()]。递归解法通过跟踪开闭括号数量来保证合法性def generateParenthesis(n): def backtrack(current, open_count, close_count): if len(current) 2*n: result.append(current) return if open_count n: backtrack(current(, open_count1, close_count) if close_count open_count: backtrack(current), open_count, close_count1) result [] backtrack(, 0, 0) return result4.3 递归目录遍历在文件系统操作中递归遍历目录是最自然的实现方式伪代码def traverse_directory(path): for entry in os.listdir(path): full_path os.path.join(path, entry) if os.path.isdir(full_path): traverse_directory(full_path) # 递归调用 else: process_file(full_path)需要注意的是实际应用中应该添加对符号链接和权限异常的处理避免无限递归或安全漏洞。5. 动态规划的优化技巧5.1 状态压缩当DP状态只依赖有限的前几个状态时可以大幅减少空间复杂度。以斐波那契数列为例我们只需要保存前两个状态def fib_optimized(n): if n 1: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b5.2 滚动数组对于二维DP问题如果当前行只依赖前一行可以使用两行数组交替更新def knapsack_rolling_array(W, wt, val, n): dp [[0]*(W1) for _ in range(2)] for i in range(1, n1): curr, prev i % 2, (i-1) % 2 for w in range(1, W1): if wt[i-1] w: dp[curr][w] max(val[i-1] dp[prev][w-wt[i-1]], dp[prev][w]) else: dp[curr][w] dp[prev][w] return dp[n % 2][W]5.3 记忆化搜索这是介于递归和DP之间的方法保留递归结构但通过缓存避免重复计算def fib_memo(n, memo{}): if n 1: return n if n not in memo: memo[n] fib_memo(n-1, memo) fib_memo(n-2, memo) return memo[n]记忆化搜索特别适合状态转移不规则或难以用迭代方式表达的问题。6. 常见错误与调试技巧6.1 递归常见陷阱栈溢出递归深度过大导致调用栈溢出。解决方法包括转换为迭代版本使用尾递归优化但Python不支持增加递归深度限制sys.setrecursionlimit()重复计算同一子问题被反复计算。解决方法添加记忆化缓存改用动态规划基线条件缺失忘记处理递归终止条件导致无限递归。6.2 DP调试技巧打印DP表格这是理解DP运行过程的最直接方式def print_dp_table(dp): for row in dp: print( .join(f{num:2} for num in row))小规模测试先用小输入测试确保基础情况正确。边界检查特别注意数组索引是否越界特别是当i0或j0时。逆向推导从最终结果回溯验证状态转移的正确性。调试心得当DP结果不符合预期时我通常会先手动计算小规模例子的正确结果然后逐步打印DP表格的中间状态找出第一个出现错误的位置这往往能快速定位问题所在。