动态规划核心思想与五大经典问题解析-开发者社区

1. 动态规划的本质与核心思想

动态规划（Dynamic Programming）这个术语听起来高大上，但它的核心思想其实非常接地气。我第一次真正理解动态规划是在解决爬楼梯问题时——假设你每次可以迈1级或2级台阶，问到第n级台阶有多少种走法。这个问题如果用暴力递归求解，时间复杂度会呈指数级增长，但当我把中间结果存储起来重复利用时，效率立刻提升了几个数量级。

动态规划之所以高效，关键在于它解决了重叠子问题（Overlapping Subproblems）和最优子结构（Optimal Substructure）这两个核心痛点。以经典的斐波那契数列为例，计算fib(5)需要重复计算fib(3)多次，这就是典型的重叠子问题。而最优子结构意味着大问题的最优解可以由小问题的最优解推导出来，就像搭积木一样层层构建。

关键认知：动态规划不是某种具体的算法，而是一种方法论。它通过"记忆化存储+递推关系"的组合拳，将指数级复杂度的问题降维到多项式级别。

在企业面试中，90%的动态规划问题可以归结为以下三种类型：

计数问题（如爬楼梯、路径规划）
最值问题（如背包问题、股票买卖）
存在性问题（如子集和问题）

2. 正向递推 vs 逆向递推：两种思维模式的对决

2.1 正向递推（自底向上）

正向递推是动态规划最常用的实现方式，也是面试官最期待看到的解法。以经典的01背包问题为例（给定物品重量和价值，在容量限制下求最大价值），正向递推的步骤如下：

定义dp数组：dp[i][j]表示前i个物品在容量j时的最大价值
初始化：dp[0][...] = 0（没有物品时价值为0）

状态转移：

if j >= weight[i-1]: dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]] + value[i-1]) else: dp[i][j] = dp[i-1][j]

最终结果：dp[n][capacity]

避坑指南：数组下标从0还是1开始常常是bug源头。建议统一采用"前i个物品"对应数组下标i-1的约定，并在代码注释中明确说明。

2.2 逆向递推（自顶向下）

逆向递推更符合人类自然思维，通常用递归+记忆化实现。还是以背包问题为例：

memo = {} def knapsack(i, j): if (i, j) in memo: return memo[(i, j)] if i == 0: return 0 if weight[i-1] > j: res = knapsack(i-1, j) else: res = max(knapsack(i-1, j), knapsack(i-1, j-weight[i-1]) + value[i-1]) memo[(i, j)] = res return res

实际工程中，当问题状态空间稀疏时（如某些坐标型DP），逆向递推可能更节省内存。但在面试场景下，除非明确要求，否则建议优先展示正向递推解法，因为：

避免了递归栈溢出的风险
更容易分析时间复杂度
代码结构更符合面试官的阅读习惯

3. 五大经典问题的深度剖析

3.1 01背包问题变形实战

原始01背包问题可能过于基础，但它的变形题却频繁出现在大厂面试中。来看这道字节跳动2023年的真题：

"给定一个只包含正整数的非空数组，判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。"

这实际上是背包问题的变种——子集和问题。解法如下：

def canPartition(nums): total = sum(nums) if total % 2 != 0: return False target = total // 2 dp = [False] * (target + 1) dp[0] = True for num in nums: for j in range(target, num - 1, -1): dp[j] = dp[j] or dp[j - num] return dp[target]

关键点在于：

识别出这实际上是求sum/2容量的背包能否被恰好装满
内层循环需要倒序更新，避免同一物品被重复使用
空间优化到O(target)而不是O(n×target)

3.2 股票买卖系列问题

这个系列问题堪称动态规划的"试金石"。以最复杂的「买卖股票的最佳时机 IV」（最多完成k笔交易）为例，其状态转移方程需要三维DP：

def maxProfit(k, prices): if not prices: return 0 n = len(prices) if k >= n // 2: # 相当于无限次交易 return sum(max(0, prices[i] - prices[i-1]) for i in range(1, n)) dp = [[[0] * 2 for _ in range(k+1)] for __ in range(n)] for i in range(n): for j in range(k, 0, -1): if i == 0: dp[i][j][0] = 0 dp[i][j][1] = -prices[i] else: dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]) dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]) return dp[n-1][k][0]

这个问题的难点在于状态定义：

dp[i][j][0]：第i天结束时，最多进行j次交易且不持有股票的最大利润
dp[i][j][1]：第i天结束时，最多进行j次交易且持有股票的最大利润

3.3 最长公共子序列(LCS)

LCS问题是字符串处理中的经典DP应用。微软2022年面试中曾出现过这样的变种：

"给定三个字符串s1、s2、s3，判断s3是否可以被s1和s2的交错组成。"

解法需要扩展经典的二维DP到三维：

def isInterleave(s1, s2, s3): m, n = len(s1), len(s2) if m + n != len(s3): return False dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True for i in range(m + 1): for j in range(n + 1): if i > 0: dp[i][j] |= dp[i-1][j] and s1[i-1] == s3[i+j-1] if j > 0: dp[i][j] |= dp[i][j-1] and s2[j-1] == s3[i+j-1] return dp[m][n]

3.4 编辑距离问题

编辑距离(Levenshtein Distance)是文本处理的基础算法。美团2023年面试中曾要求实现支持权重不同的编辑距离计算：

def minDistance(word1, word2, insert_cost, delete_cost, replace_cost): m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i * delete_cost for j in range(n + 1): dp[0][j] = j * insert_cost for i in range(1, m + 1): for j in range(1, n + 1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min( dp[i][j-1] + insert_cost, dp[i-1][j] + delete_cost, dp[i-1][j-1] + replace_cost ) return dp[m][n]

3.5 打家劫舍系列

这个系列问题考察对状态定义的灵活运用。最复杂的变种是「打家劫舍 III」——房屋排列成二叉树结构。以下是Google面试中的解法：

def rob(root): def dfs(node): if not node: return (0, 0) left = dfs(node.left) right = dfs(node.right) rob_current = node.val + left[1] + right[1] not_rob = max(left) + max(right) return (rob_current, not_rob) return max(dfs(root))

这里返回的元组第一个元素表示抢劫当前节点的最大收益，第二个表示不抢劫当前节点的最大收益。这种后序遍历的DFS+DP组合在树形DP中非常常见。

4. 企业真题实战解析

4.1 字节跳动2023：最短覆盖子串

"给定一个字符串s和一个字符串集合words，words中所有字符串长度相同。找出s中包含words中所有字符串（顺序不限）的最短子串。"

这实际上是滑动窗口与DP的结合题。关键点在于：

用哈希表记录words的词频
滑动窗口维护当前窗口的词频
DP思想体现在对固定长度单词的处理上

def findSubstring(s, words): from collections import defaultdict if not s or not words: return "" word_len = len(words[0]) total_len = word_len * len(words) word_count = defaultdict(int) for word in words: word_count[word] += 1 res = [] for i in range(word_len): left = i curr_count = defaultdict(int) count = 0 for j in range(i, len(s) - word_len + 1, word_len): word = s[j:j+word_len] if word in word_count: curr_count[word] += 1 count += 1 while curr_count[word] > word_count[word]: left_word = s[left:left+word_len] curr_count[left_word] -= 1 left += word_len count -= 1 if count == len(words): res.append(s[left:j+word_len]) else: curr_count.clear() count = 0 left = j + word_len return min(res, key=len) if res else ""

4.2 腾讯2023：游戏路径规划

"在n×m的网格中，每个格子有不同数量的金币。从左上角出发，每次只能向右或向下移动，求到右下角时能收集的最大金币数。"

这是典型的二维坐标型DP：

def maxGold(grid): if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) dp = [[0] * n for _ in range(m)] dp[0][0] = grid[0][0] for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0] for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j] for i in range(1, m): for j in range(1, n): dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j] return dp[m-1][n-1]

空间优化版本（滚动数组）：

def maxGold(grid): if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) dp = [0] * n dp[0] = grid[0][0] for j in range(1, n): dp[j] = dp[j-1] + grid[0][j] for i in range(1, m): dp[0] += grid[i][0] for j in range(1, n): dp[j] = max(dp[j], dp[j-1]) + grid[i][j] return dp[-1]

4.3 阿里2023：订单分配优化

"有n个订单和m个骑手，每个订单有配送费，每个骑手最多接k个订单。求最大总配送费。"

这实际上是二分图带权匹配问题，可以用DP解决：

def maxProfit(orders, m, k): n = len(orders) orders.sort(reverse=True) dp = [[0] * (k + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, k + 1): idx = (i - 1) * k + (j - 1) if idx >= n: dp[i][j] = dp[i][j-1] else: dp[i][j] = max(dp[i][j-1] + orders[idx], dp[i-1][k]) return dp[m][k]

4.4 美团2023：优惠券组合

"给定不同面额的优惠券和总金额amount，计算可以凑成总金额的最少优惠券数。每种优惠券可以使用多次。"

这是完全背包问题的变种：

def coinChange(coins, amount): dp = [float('inf')] * (amount + 1) dp[0] = 0 for coin in coins: for j in range(coin, amount + 1): dp[j] = min(dp[j], dp[j - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1

5. 动态规划的优化技巧

5.1 状态压缩

当DP状态只依赖前几个状态时，可以用滚动数组减少空间复杂度。比如斐波那契数列：

def fib(n): if n < 2: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b

5.2 斜率优化

对于形如dp[i] = min(dp[j] + cost(j,i))的转移方程，当cost函数满足单调性时，可以用单调队列优化：

def minCost(nums, k): from collections import deque n = len(nums) dp = [0] * (n + 1) q = deque() q.append(0) for i in range(1, n + 1): while q and q[0] < i - k: q.popleft() dp[i] = dp[q[0]] + nums[i-1] while q and dp[i] <= dp[q[-1]]: q.pop() q.append(i) return dp[n]

5.3 四边形不等式

对于区间DP问题，当决策点具有单调性时，可以优化时间复杂度：

def stoneGame(stones): n = len(stones) prefix = [0] * (n + 1) for i in range(n): prefix[i + 1] = prefix[i] + stones[i] dp = [[0] * n for _ in range(n)] s = [[0] * n for _ in range(n)] for i in range(n): s[i][i] = i for l in range(2, n + 1): for i in range(n - l + 1): j = i + l - 1 mn = float('inf') for k in range(s[i][j - 1], s[i + 1][j] + 1): cost = dp[i][k] + dp[k + 1][j] + prefix[j + 1] - prefix[i] if cost < mn: mn = cost s[i][j] = k dp[i][j] = mn return dp[0][n - 1]

5.4 树形DP优化

对于树形DP，可以通过后序遍历+记忆化减少计算量：

def treeDiameter(edges): from collections import defaultdict tree = defaultdict(list) for u, v in edges: tree[u].append(v) tree[v].append(u) diameter = 0 def dfs(node, parent): nonlocal diameter max1 = max2 = 0 for neighbor in tree[node]: if neighbor == parent: continue depth = dfs(neighbor, node) if depth > max1: max2, max1 = max1, depth elif depth > max2: max2 = depth diameter = max(diameter, max1 + max2) return max1 + 1 dfs(0, -1) return diameter

6. 动态规划的常见误区

6.1 过度设计状态

新手常犯的错误是设计过于复杂的状态。比如在解决"最长递增子序列"时，有人会定义dp[i][j]表示前i个数中以j结尾的最长序列，这导致不必要的复杂度。正确的状态定义应该是：

def lengthOfLIS(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)

6.2 忽略边界条件

DP问题对边界条件极其敏感。比如在"不同路径"问题中，忘记初始化第一行和第一列会导致错误：

def uniquePaths(m, n): dp = [[1] * n for _ in range(m)] for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[m-1][n-1]

6.3 错误的空间优化

在进行空间优化时，更新顺序很重要。比如完全背包问题内层需要正序循环：

def change(amount, coins): dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: for j in range(coin, amount + 1): dp[j] += dp[j - coin] return dp[amount]

而01背包则需要倒序循环，这是新手最容易混淆的点。

6.4 混淆问题类型

有些问题看似相似实则不同。比如"连续子数组最大和"与"允许删除一个元素的连续子数组最大和"：

# 标准版本 def maxSubArray(nums): dp = [0] * len(nums) dp[0] = nums[0] for i in range(1, len(nums)): dp[i] = max(nums[i], dp[i-1] + nums[i]) return max(dp) # 允许删除一个元素 def maximumSum(arr): n = len(arr) if n == 1: return arr[0] dp1 = [0] * n # 未删除 dp2 = [0] * n # 已删除 dp1[0] = arr[0] res = arr[0] for i in range(1, n): dp1[i] = max(arr[i], dp1[i-1] + arr[i]) dp2[i] = max(dp1[i-1], dp2[i-1] + arr[i]) res = max(res, dp1[i], dp2[i]) return res

7. 动态规划的系统训练方法

7.1 问题分类训练法

我建议按照以下分类进行专项突破：

线性DP（LIS、LCS、最大子数组和）
区间DP（石子合并、回文分割）
背包问题（01背包、完全背包、多重背包）
状态机DP（股票买卖、打家劫舍）
树形DP（二叉树最大路径和、监控二叉树）
数位DP（数字1的个数、不含连续1的非负整数）

7.2 解题四步法

面对新问题时，按以下步骤思考：

定义状态：明确dp数组的含义
确定转移：分析状态之间的关系
初始化：设置边界条件
确定输出：明确最终结果的位置

7.3 代码模板化

将常见DP模式抽象为模板。比如背包问题的通用模板：

def knapsack_template(weights, values, capacity): n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(capacity + 1): if j >= weights[i-1]: dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]) else: dp[i][j] = dp[i-1][j] return dp[n][capacity]

7.4 错题分析法

建立错题本，记录以下信息：

错误的状态定义
遗漏的边界条件
错误的时间复杂度分析
更优的解法思路

动态规划核心思想与五大经典问题解析