Dynamic programming 面试题
动态规划（DP）是顶级科技公司编码面试中测试的核心算法范式。它评估你将复杂问题分解为重叠子问题并使用记忆化或制表法的能力。DP 问题通常涉及优化、序列和组合问题。它们经常出现在 FAANG 和其他顶级公司的面试中。
Dynamic programming 面试涵盖内容
记忆化 vs 制表法
理解自顶向下（递归+记忆化）和自底向上（制表法）方法、它们的权衡以及何时使用每种方法。
常见 DP 模式
掌握经典模式如斐波那契、背包、最长公共子序列和矩阵链乘，以快速识别 DP 问题。
状态定义与转移
学习如何定义 DP 状态（例如 dp[i][j]）并制定正确表达问题约束的递推关系。
优化技巧
使用空间优化（例如滚动数组）、单调队列和其他技术来减少 DP 解决方案中的内存和运行时间。
Dynamic programming 面试题示例
- 解释 DP 中记忆化和制表法的区别。好回答应覆盖
- 记忆化是自顶向下的方法，在递归中缓存计算结果以避免重复计算。
- 制表法是自底向上的方法，通过迭代填充表格来求解子问题。
- 记忆化通常使用递归和哈希表（如字典）实现，而制表法使用数组或矩阵。
- 记忆化可能因为递归深度导致栈溢出，制表法通常更高效且易于实现。
- 两者都基于重叠子问题和最优子结构，但实现方式和性能特征不同。
查看范例答案
记忆化（Memoization）和制表法（Tabulation）都是动态规划中用于优化递归或迭代求解的技术。记忆化采用自顶向下的方式，从原问题出发递归地分解为子问题，并在递归过程中将已计算的子问题结果存储起来（如使用哈希表或数组），避免重复计算。制表法采用自底向上的方式，先求解最小的子问题，然后逐步构建更大子问题的解，通常通过迭代填充一个表格（如一维或二维数组）来实现。记忆化的优点是只需要求解实际需要的子问题，可能节省空间，但递归调用可能带来额外的函数调用开销和栈溢出风险；制表法则通常更高效，因为它的迭代实现避免了递归开销，且空间复杂度易于控制。两者都需要问题具有重叠子问题和最优子结构性质。在实际应用中，制表法更容易调试和实现，但记忆化有时更直观。选择哪种方法取决于具体场景，例如递归深度、子问题的依赖关系以及程序员偏好。
- 使用 DP（自顶向下和自底向上）实现斐波那契数。好回答应覆盖
- 斐波那契数列定义为 F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。
- 自顶向下使用递归加记忆化，缓存已经计算过的值。
- 自底向上使用迭代，从基底开始逐步计算到目标值。
- 自顶向下的优势是仅计算需要的子问题，自底向上则通常空间效率更高。
- 两种方法的时间复杂度均为 O(n)，空间复杂度为 O(n) 或可优化到 O(1)。
查看范例答案
斐波那契数列是动态规划的经典入门问题。自顶向下的做法是通过递归函数，并在递归前检查缓存中是否已有结果，若无则递归计算并存储。自底向上的做法是使用数组从 F(0) 和 F(1) 开始，依次计算每一项到目标值。两种方法的时间复杂度都是 O(n)，因为每个子问题只计算一次。空间复杂度上，自顶向下需要 O(n) 的递归栈空间和缓存，自底向上如果只保留前两项则可优化到 O(1)。自底向上的迭代实现通常更高效，因为它避免了递归调用开销和栈溢出风险，但自顶向下的思路更直观，容易从递归关系推导。在实际面试中，应当首先给出自底向上的迭代解，并考虑状态压缩以展示优化能力。
参考代码python # 自顶向下（记忆化） def fib_memo(n: int) -> int: memo = {0: 0, 1: 1} def helper(k): if k not in memo: memo[k] = helper(k-1) + helper(k-2) return memo[k] return helper(n) # 自底向上（制表法） def fib_tab(n: int) -> int: if n <= 1: return n dp = [0] * (n + 1) dp[0], dp[1] = 0, 1 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n] # 空间优化自底向上 def fib_opt(n: int) -> int: if n <= 1: return n a, b = 0, 1 for _ in range(2, n + 1): a, b = b, a + b return b # 时间复杂度：O(n)，空间复杂度：记忆化 O(n) + 递归栈，制表法 O(n)，优化 O(1) - 给定一组具有重量和价值的物品，求解 0/1 背包问题以获取最大价值。好回答应覆盖
- 0/1 背包问题中每个物品只能取一次，目标是最大化总价值且总重量不超过容量。
- 定义 dp[i][w] 为考虑前 i 个物品、容量为 w 时的最大价值。
- 状态转移：dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi) 当 wi <= w。
- 优化空间可改用一维数组，但需从大到小遍历容量以避免重复使用物品。
- 初始化 dp[0][w]=0，最终答案为 dp[n][capacity]。
查看范例答案
0/1 背包问题是动态规划的典型应用。我们定义 dp[i][w] 表示在前 i 个物品中，选取总重量不超过 w 的最大价值。状态转移考虑第 i 个物品选或不选：不选则是 dp[i-1][w]；选则需要满足重量 wi <= w，价值为 dp[i-1][w-wi] + vi。因此 dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi] + vi)（当 wi <= w）。基础情况为 dp[0][w]=0（没有物品时价值为0）。为了优化空间，可以使用一维数组 dp[w]，但内层循环需从大到小遍历容量，以保证每个物品只被考虑一次。时间复杂度为 O(n*capacity)，空间复杂度可优化至 O(capacity)。注意容量和物品数量较大时，空间优化尤为重要。此外，如果要求输出具体选取的物品，则需保留二维数组或额外记录路径。
参考代码python def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int: n = len(weights) # 一维 DP 数组，容量从 0 到 capacity 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] # 示例：weights = [2,3,4,5], values = [3,4,5,6], capacity=8 → 返回 10 # 时间复杂度：O(n*capacity)，空间复杂度：O(capacity) - 在数组中找到最长递增子序列的长度。好回答应覆盖
- 最长递增子序列（LIS）不要求连续，但元素顺序与原数组一致。
- 动态规划解：dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。
- 转移方程：dp[i] = 1 + max(dp[j]) 对于所有 j < i 且 nums[j] < nums[i]。
- 时间复杂度 O(n^2)，可用二分查找优化到 O(n log n)。
- 最终答案是所有 dp[i] 的最大值。
查看范例答案
最长递增子序列问题要求找出数组中最长的严格递增子序列（不一定连续）。动态规划解法中，定义 dp[i] 为以 nums[i] 结尾的最长递增子序列的长度。对于每个 i，遍历所有 j < i，如果 nums[j] < nums[i]，则 dp[i] = max(dp[i], dp[j] + 1)；另外，每个元素自身可以作为一个长度为1的子序列，所以 dp[i] 初始化为1。最终答案取所有 dp[i] 的最大值。该方法时间复杂度为 O(n^2)，空间复杂度 O(n)。对于更大的输入，可以使用贪心加二分查找的方法优化到 O(n log n)：维护一个数组 tails，其中 tails[k] 表示长度为 k+1 的递增子序列的末尾元素的最小值。遍历每个元素，通过二分查找找到它在 tails 中的位置并更新。注意，两种方法都要处理空数组的边界情况。面试中可以先给出 O(n^2) 的解再展示优化。
参考代码python # DP O(n^2) 解法 def length_of_LIS_dp(nums: list[int]) -> int: if not nums: return 0 n = len(nums) dp = [1] * n for i in range(n): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) # 贪心+二分 O(n log n) 解法 def length_of_LIS_binary(nums: list[int]) -> int: import bisect tails = [] for x in nums: i = bisect.bisect_left(tails, x) if i == len(tails): tails.append(x) else: tails[i] = x return len(tails) # 时间复杂度：DP O(n^2)，二分 O(n log n)；空间复杂度：O(n) - 计算两个字符串之间的编辑距离（Levenshtein 距离）。好回答应覆盖
- 编辑距离（Levenshtein 距离）指将字符串 A 变为 B 所需的最少操作数，操作包括插入、删除、替换。
- 定义 dp[i][j] 为 A[0..i-1] 到 B[0..j-1] 的编辑距离。
- 初始化 dp[i][0]=i, dp[0][j]=j。
- 转移：若 A[i-1]==B[j-1]，则 dp[i][j]=dp[i-1][j-1]；否则取三种操作的最小值加1。
- 空间可优化为 O(min(m,n))，但通常二维数组易于理解。
查看范例答案
编辑距离问题是计算将一个字符串转换成另一个所需的最少单字符编辑操作（插入、删除、替换）次数。动态规划解法使用二维数组 dp，其中 dp[i][j] 表示字符串 A 的前 i 个字符到 B 的前 j 个字符的编辑距离。初始化时，dp[i][0]=i（删除 i 次），dp[0][j]=j（插入 j 次）。状态转移时，如果 A[i-1] == B[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])，分别对应删除、插入、替换操作。最终答案为 dp[m][n]。时间复杂度 O(m*n)，空间复杂度 O(m*n)，可优化为两行或一行。注意空字符串的边界情况。
参考代码python def edit_distance(word1: str, word2: str) -> int: m, n = len(word1), len(word2) # 创建二维 dp 数组 dp = [[0] * (n + 1) for _ in range(m + 1)] # 初始化第一行和第一列 for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j # 填充 dp 表格 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] = 1 + min(dp[i-1][j], # 删除 dp[i][j-1], # 插入 dp[i-1][j-1]) # 替换 return dp[m][n] # 示例：edit_distance("horse", "ros") → 3 # 时间复杂度 O(m*n)，空间复杂度 O(m*n) - 解决硬币找零问题：用最少数量的硬币凑出给定金额。好回答应覆盖
- 硬币找零问题：给定不同面值的硬币和一个总金额，求组成该金额所需的最少硬币数。
- 假设每种硬币数量无限（完全背包问题）。
- 定义 dp[i] 为凑成金额 i 所需的最少硬币数，dp[0]=0。
- 转移方程：dp[i] = min(dp[i - coin] + 1) 对于所有 coin 且 coin <= i。
- 初始化 dp 为一个大数（如 inf），最终 dp[amount] 若仍为 inf 则返回 -1。
查看范例答案
硬币找零问题是一个典型的完全背包动态规划问题。我们定义 dp[i] 为凑成总金额 i 所需的最少硬币数。初始化 dp[0]=0，其余 dp[i] 设为正无穷（表示不可达）。对于每个金额 i，遍历所有硬币面值 coin，如果 coin <= i，则更新 dp[i] = min(dp[i], dp[i - coin] + 1)。最终 dp[amount] 即为答案；若 dp[amount] 仍为无穷大，说明无法凑出该金额，返回 -1。时间复杂度为 O(amount * 硬币种类数)，空间复杂度 O(amount)。注意硬币面值可能包含重复或非递增顺序，但通常不影响结果。一个常见的陷阱是：如果硬币面值没有1，可能出现无法凑足的情况。另外，因为硬币数量无限，内层循环金额可以从小到大遍历（完全背包顺序），但这里 dp[i] 依赖于 dp[i-coin]，所以从小到大正确。
参考代码python def coin_change(coins: list[int], amount: int) -> int: # 初始化 dp 数组，大小为 amount+1，填充一个大数 INF = float('inf') dp = [INF] * (amount + 1) dp[0] = 0 # 遍历每个金额 for i in range(1, amount + 1): for coin in coins: if coin <= i: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != INF else -1 # 示例：coins=[1,2,5], amount=11 → 3 (5+5+1) # 时间复杂度 O(amount * len(coins))，空间复杂度 O(amount) - 计算每次走 1 或 2 步爬楼梯的方法数。好回答应覆盖
- 爬楼梯问题等价于斐波那契数列：每次可走1步或2步，到达第n阶的方法数。
- 定义 dp[i] 为到达第 i 阶的方法数，dp[1]=1, dp[2]=2。
- 转移方程：dp[i] = dp[i-1] + dp[i-2]。
- 可优化空间到 O(1) 只保留前两个状态。
- 注意 n 从1开始，当 n<=2 时直接返回 n。
查看范例答案
爬楼梯问题是一个简单的动态规划问题，实际上是斐波那契数列的应用。设 dp[i] 表示爬到第 i 级台阶的方法数。由于每次只能走1步或2步，要到达第 i 级，可以从第 i-1 级走1步，或从第 i-2 级走2步，因此状态转移方程为 dp[i] = dp[i-1] + dp[i-2]。基础情况：dp[1]=1（只有一种走法），dp[2]=2（两次1步或一次2步）。对于 n 较小的情况，可以直接返回 n。空间上可以优化到只用两个变量保存前两个状态，因为每次迭代只依赖前两个值。时间复杂度为 O(n)，空间复杂度 O(1)。注意题目有时会约定 n 为正整数，需考虑 n=0 的边界（通常为1种方法）。
参考代码python def climb_stairs(n: int) -> int: if n <= 2: return n a, b = 1, 2 # a = dp[1], b = dp[2] for _ in range(3, n + 1): a, b = b, a + b return b # 示例：n=5 → 8 # 时间复杂度 O(n)，空间复杂度 O(1) - 描述解决任何 DP 问题的逐步方法，从识别子问题到编码解决方案。好回答应覆盖
- 第一步：识别问题是否具有最优子结构和重叠子问题，确定是否适用 DP。
- 第二步：定义状态，即子问题的表示，通常使用一维或多维数组。
- 第三步：推导状态转移方程，明确当前状态与之前状态的关系。
- 第四步：确定基础情况（边界条件）和遍历顺序（自顶向下或自底向上）。
- 第五步：实现代码，考虑空间优化（如滚动数组），并分析时间和空间复杂度。
查看范例答案
解决任何动态规划问题的系统方法通常包含以下几个步骤：首先，分析问题是否具有最优子结构（即问题的最优解包含子问题的最优解）和重叠子问题（即子问题被重复计算），如果满足则考虑使用 DP。其次，定义状态，即用变量表示子问题，例如 dp[i] 或 dp[i][j]，需要谨慎选择状态维度以保证完整描述问题。第三，推导状态转移方程，这是核心步骤，需要找出当前状态如何从更小的子问题转移而来，通常通过“选择或不选择”、“插入/删除/替换”等决策来描述。第四，确定基础情况（如初始值）和遍历顺序：自顶向下需递归加记忆化，自底向上需迭代填充。最后，编码实现时注意边界条件，考虑空间优化（如使用滚动数组减少空间），并分析最终的时间和空间复杂度。一个常见的陷阱是状态定义不准确导致遗漏合理解，或者忽略基础情况导致溢出。实际面试中，建议先通过画图或举例说明递推关系，再逐步写出代码。
如何准备
- 掌握常见 DP 模式，如背包、LCS 和网格问题。
- 在编码之前练习从零开始编写递推关系。
- 从暴力递归开始，然后添加记忆化，如果需要再转换为制表法。
- 使用空间优化技术（例如将二维 DP 降为一维）来提高效率。
- 每个模式至少解决 3-4 个问题，以建立识别 DP 的直觉。
常见问题
DP 和递归的关键区别是什么？
DP 存储子问题的结果以避免重复计算，而不带记忆化的递归可能会多次求解相同的子问题。
如何知道一个问题可以用 DP 解决？
如果问题具有重叠子问题和最优子结构（可以从子问题的最优解构建最优解），则 DP 适用。
面试中应该使用记忆化还是制表法？
记忆化通常更容易实现自顶向下，但制表法可能更节省空间且避免递归深度。根据熟悉程度和问题约束选择。
最常见的 DP 面试问题有哪些？
背包、区间 DP、序列比对（LCS、编辑距离）、矩阵链乘和树形 DP 经常被问到。
如何快速提高 DP 技能？
练习将问题分类到模式中，每个模式解决 5-10 个问题，并复习递推关系以建立状态转移的直觉。
练习 Dynamic programming 题目，即时获取 AI 反馈
上传简历，获得个性化模拟面试，并了解需要改进的地方——免费开始。