从暴力递归到记忆化搜索再到DP表——动态规划是算法面试的半壁江山
动态规划（Dynamic Programming, DP）是将复杂问题拆解为重叠子问题，通过记忆化避免重复计算的算法范式。DP是算法面试中最重要的主题——在LeetCode中DP题目超过500道，是出题频率最高的算法类型。
# 暴力递归 O(2^n) — 大量重复计算
def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)
# 记忆化搜索 O(n) — 自顶向下 + 缓存
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)
# 动态规划 O(n) — 自底向上填表
def fib(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n+1):
a, b = b, a + b
return b
# 矩阵快速幂 O(log n) — 进阶
def fib(n):
if n <= 1: return n
def mul(A, B):
return [[A[0][0]*B[0][0]+A[0][1]*B[1][0],
A[0][0]*B[0][1]+A[0][1]*B[1][1]],
[A[1][0]*B[0][0]+A[1][1]*B[1][0],
A[1][0]*B[0][1]+A[1][1]*B[1][1]]]
def pow_m(M, n):
if n == 1: return M
h = pow_m(M, n//2)
return mul(mul(h,h), M) if n%2 else mul(h,h)
return pow_m([[1,1],[1,0]], n)[0][1]| 类型 | 代表题目 | 难度 |
|---|---|---|
| 线性DP | 爬楼梯、打家劫舍 | 入门 |
| 背包DP | 01背包、完全背包 | 中等 |
| 子序列DP | LCS、LIS | 中等 |
| 路径DP | 最小路径和、不同路径 | 入门 |
| 字符串DP | 编辑距离、正则匹配 | 较难 |
| 树形DP | 打家劫舍III | 中等 |
| 状态压缩DP | 旅行商、棋盘覆盖 | 困难 |
每次可以爬1或2个台阶，爬到第n阶有多少种不同方法？
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return b
# 完整DP版本（便于理解）
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]时间: O(n) 空间: O(1)（滚动数组优化后）
给定数组 cost，cost[i]是从第i个台阶向上爬的花费，可以从下标0或1开始，求到达顶部的最小花费。
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
dp = [0] * (n + 1)
for i in range(2, n + 1):
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
return dp[n]
# 空间优化版本
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
a, b = 0, 0
for c in cost:
a, b = b, min(a, b) + c
return min(a, b)时间: O(n) 空间: O(n)，可优化到O(1)
给定非负整数数组，代表各房屋金额，不能偷相邻房屋，求能偷到的最大金额。
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) <= 2:
return max(nums)
prev2, prev1 = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
return prev1
# 带dp数组版本（更清晰）
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 0: return 0
if n == 1: return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[n-1]时间: O(n) 空间: O(1)
在实际面试中，算法题不仅仅是写代码，更考察沟通、分析和解决问题的能力。以下是一些实战技巧：
# 通用解题模板
class Solution:
def solve(self, input_data):
# 1. 边界检查
if not input_data:
return default_value
# 2. 初始化
result = initial_value
state = initial_state
# 3. 主循环
for item in input_data:
state = transition(state, item)
result = max/min/update(result, state)
# 4. 返回结果
return result