预计阅读 36 分钟
算法设计三板斧 —— 动态规划、贪心与回溯
动态规划教你”记住过去的教训”，贪心教你”抓住眼前的最优”，回溯教你”此路不通就退回来”。掌握这三种思想，你就拥有了解决绝大多数算法问题的核心武器。
📋 开篇自测：你已经知道多少？
- 爬楼梯问题（每次走1步或2步，走到第n级有多少种走法）你能用两种不同的方法解出来吗？
- 为什么贪心算法有时候能找到最优解，有时候不能？你能举一个贪心失效的例子吗？
- 八皇后问题为什么用暴力穷举几乎不可能解决，但用回溯法却可以高效解决？
一、动态规划——把大问题拆成小问题，记住每个小问题的答案
从一个经典问题说起
爬楼梯问题： 一共n级台阶，你每次可以走1级或2级，请问走到第n级有多少种不同的走法？
先用最直觉的方法——递归：
def climb_stairs_naive(n):
"""递归解法（会超时）"""
if n <= 2:
return n
return climb_stairs_naive(n - 1) + climb_stairs_naive(n - 2)这段代码逻辑完全正确，但当n=40时你可能需要等好几秒，n=50时可能要等几分钟。为什么？
画出递归树你就明白了：
f(5)
/ \
f(4) f(3)
/ \ / \
f(3) f(2) f(2) f(1)
/ \
f(2) f(1)看到了吗？f(3)被计算了2次，f(2)被计算了3次。当n更大时，重复计算的量呈指数级爆炸。这就是递归的致命缺陷——重叠子问题。
动态规划的核心思想
动态规划（Dynamic Programming，简称DP）的核心就两句话：
- 把大问题拆解为重叠的子问题
- 记住每个子问题的答案，避免重复计算
这就像考试前的复习策略：你不会每次做到同一个题型都从头推导公式，而是第一次推导后就把公式记在本子上，下次直接查。
方法一：自顶向下（记忆化递归）
递归的结构不变，但用一个字典把已经算过的结果存起来。
def climb_stairs_memo(n, memo=None):
"""记忆化递归"""
if memo is None:
memo = {}
if n <= 2:
return n
if n in memo:
return memo[n] # 已经算过，直接返回
memo[n] = climb_stairs_memo(n - 1, memo) + climb_stairs_memo(n - 2, memo)
return memo[n]
print(climb_stairs_memo(50)) # 12586269025，瞬间出结果方法二：自底向上（表格法）
不用递归，从最小的子问题开始，逐步推导出大问题的答案。
def climb_stairs_dp(n):
"""自底向上的动态规划"""
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(climb_stairs_dp(50)) # 12586269025还可以进一步优化空间——因为每一步只依赖前两步的结果，不需要整个数组：
def climb_stairs_optimized(n):
"""空间优化版"""
if n <= 2:
return n
prev2, prev1 = 1, 2
for i in range(3, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1🤔 想一想 爬楼梯问题的递推公式
f(n) = f(n-1) + f(n-2)其实就是斐波那契数列。你能想到其他遵循类似递推关系的现实问题吗？
二、动态规划实战——经典问题解析
问题1：背包问题——有限预算下的最优选择
你要去徒步旅行，背包最多能装15公斤。有以下物品：
| 物品 | 重量(kg) | 价值 |
|---|---|---|
| 帐篷 | 5 | 60 |
| 睡袋 | 3 | 50 |
| 食物 | 4 | 70 |
| 水壶 | 2 | 30 |
| 急救包 | 1 | 20 |
如何选择物品使总价值最大？
def knapsack(weights, values, capacity):
"""0-1背包问题"""
n = len(weights)
# dp[i][w] 表示：考虑前i个物品、容量为w时的最大价值
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
# 不选第i个物品
dp[i][w] = dp[i - 1][w]
# 选第i个物品（前提是装得下）
if weights[i - 1] <= w:
dp[i][w] = max(dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1])
# 回溯找出选了哪些物品
selected = []
w = capacity
for i in range(n, 0, -1):
if dp[i][w] != dp[i - 1][w]:
selected.append(i - 1)
w -= weights[i - 1]
return dp[n][capacity], selected
weights = [5, 3, 4, 2, 1]
values = [60, 50, 70, 30, 20]
items = ["帐篷", "睡袋", "食物", "水壶", "急救包"]
max_value, selected = knapsack(weights, values, 15)
print(f"最大价值: {max_value}")
print(f"选择的物品: {[items[i] for i in selected]}")
# 最大价值: 230
# 选择的物品: ['急救包', '水壶', '食物', '睡袋', '帐篷']问题2：最长公共子序列（LCS）
找出两个字符串中最长的公共子序列（子序列不要求连续）。
def longest_common_subsequence(text1, text2):
"""最长公共子序列"""
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
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])
# 回溯找出具体的子序列
lcs = []
i, j = m, n
while i > 0 and j > 0:
if text1[i - 1] == text2[j - 1]:
lcs.append(text1[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1
return dp[m][n], ''.join(reversed(lcs))
length, seq = longest_common_subsequence("ABCBDAB", "BDCAB")
print(f"长度: {length}, 子序列: {seq}")
# 长度: 4, 子序列: BCAB问题3：编辑距离
两个字符串之间的”编辑距离”是从一个变成另一个所需的最少操作次数（插入、删除、替换）。这是拼写纠错、DNA序列比对的基础。
def edit_distance(word1, word2):
"""编辑距离（Levenshtein距离）"""
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始化：空串到长度为i/j的串需要i/j次操作
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
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]
print(edit_distance("kitten", "sitting")) # 3
# kitten -> sitten (替换k->s) -> sittin (替换e->i) -> sitting (插入g)动态规划解题框架
遇到动态规划问题，可以按这个框架思考：
- 定义状态： dp[i]（或dp[i][j]）代表什么含义？
- 找出递推关系： dp[i]和哪些更小的子问题有关？
- 确定边界条件： 最小的子问题，答案是什么？
- 确定计算顺序： 从小到大还是从大到小？
- （可选）优化空间
三、贪心算法——每一步都选当前最好的
核心思想
贪心算法的策略非常简单：每一步都做出当前看来最优的选择，不管未来会怎样。 它不像动态规划那样考虑全局，而是”目光短浅”地只看眼前。
神奇的是——在某些问题中，这种”目光短浅”的策略居然能得到全局最优解。
经典问题1：找零钱
你是收银员，需要用最少数量的硬币找零。硬币面值有1元、5元、10元、25元。
def make_change_greedy(amount, coins=[25, 10, 5, 1]):
"""贪心找零"""
result = []
for coin in coins: # 从大面值到小面值
count = amount // coin
if count > 0:
result.extend([coin] * count)
amount -= coin * count
return result
print(make_change_greedy(63))
# [25, 25, 10, 1, 1, 1] —— 6枚硬币对于标准面值的硬币（1, 5, 10, 25），贪心总能得到最优解。但如果硬币面值是 [1, 3, 4] 呢？
# 贪心策略对[1, 3, 4]的结果
print(make_change_greedy(6, [4, 3, 1]))
# [4, 1, 1] —— 3枚
# 但最优解是 [3, 3] —— 只要2枚！这就是贪心的局限——它不是万能的。只有当问题具有”贪心选择性质”时，贪心才能保证得到最优解。
经典问题2：活动选择
你有一系列活动，每个活动有开始和结束时间，不能同时参加两个活动。如何选择最多的活动？
def activity_selection(activities):
"""
活动选择问题
activities: [(开始时间, 结束时间), ...]
"""
# 贪心策略：按结束时间排序，优先选结束最早的活动
sorted_acts = sorted(activities, key=lambda x: x[1])
selected = [sorted_acts[0]]
last_end = sorted_acts[0][1]
for start, end in sorted_acts[1:]:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9),
(6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
result = activity_selection(activities)
print(f"最多可以参加 {len(result)} 个活动: {result}")
# 最多可以参加 4 个活动: [(1, 4), (5, 7), (8, 11), (12, 16)]为什么这里贪心能得到最优解？直觉上说：越早结束的活动越好，因为它给后面的活动留了更多时间。这个直觉可以严格证明——每一步的贪心选择都不会让后续选择变差。
经典问题3：哈夫曼编码
哈夫曼编码用贪心策略实现数据压缩——出现频率高的字符用短编码，频率低的用长编码。
import heapq
def huffman_encoding(freq):
"""
构建哈夫曼树并生成编码
freq: {'a': 45, 'b': 13, ...}
"""
# 用最小堆管理节点
heap = [[count, [char, ""]] for char, count in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
# 给lo的所有字符编码加前缀'0'
for pair in lo[1:]:
pair[1] = '0' + pair[1]
# 给hi的所有字符编码加前缀'1'
for pair in hi[1:]:
pair[1] = '1' + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
codes = {}
for pair in heap[0][1:]:
codes[pair[0]] = pair[1]
return codes
freq = {'a': 45, 'b': 13, 'c': 12, 'd': 16, 'e': 9, 'f': 5}
codes = huffman_encoding(freq)
for char, code in sorted(codes.items()):
print(f"'{char}': {code}")
# 高频字符（如'a'）的编码最短🤔 想一想 贪心和动态规划的关系是什么？可以这样理解：贪心是动态规划的一种特殊情况——当每一步的局部最优选择恰好就是全局最优的一部分时，就可以用贪心。贪心不需要考虑所有子问题，所以通常更快。
四、回溯算法——此路不通就退回来
核心思想
回溯算法本质上是一种有策略的暴力穷举。它沿着一条路径往前探索，一旦发现走不通（不满足约束条件），就退回到上一步，换一条路继续。
这就像你在迷宫里走——每到一个岔路口就选一条路走，碰到死胡同就原路返回到上一个岔路口，选另一条路。
回溯法的关键优化是剪枝——提前判断某条路不可能通向答案，直接放弃，不用走到底才发现。
经典问题1：N皇后问题
在N×N的棋盘上放N个皇后，使得任意两个皇后不在同一行、同一列、同一对角线。
def solve_n_queens(n):
"""N皇后问题"""
solutions = []
board = [-1] * n # board[i] = j 表示第i行的皇后放在第j列
def is_valid(row, col):
"""检查在(row, col)放皇后是否合法"""
for prev_row in range(row):
prev_col = board[prev_row]
# 同列
if prev_col == col:
return False
# 同对角线
if abs(prev_row - row) == abs(prev_col - col):
return False
return True
def backtrack(row):
if row == n:
solutions.append(board[:])
return
for col in range(n):
if is_valid(row, col):
board[row] = col
backtrack(row + 1)
board[row] = -1 # 回溯：撤销选择
backtrack(0)
return solutions
# 8皇后的解法数
solutions = solve_n_queens(8)
print(f"8皇后共有 {len(solutions)} 种解法") # 92
# 可视化一个解
def print_board(solution):
n = len(solution)
for row in range(n):
line = ['.'] * n
line[solution[row]] = 'Q'
print(' '.join(line))
print()
print_board(solutions[0])经典问题2：数独求解
def solve_sudoku(board):
"""解数独"""
def is_valid(board, row, col, num):
# 检查行
if num in board[row]:
return False
# 检查列
if num in [board[r][col] for r in range(9)]:
return False
# 检查3x3方格
box_row, box_col = 3 * (row // 3), 3 * (col // 3)
for r in range(box_row, box_row + 3):
for c in range(box_col, box_col + 3):
if board[r][c] == num:
return False
return True
def backtrack():
for row in range(9):
for col in range(9):
if board[row][col] == 0: # 找到空格
for num in range(1, 10):
if is_valid(board, row, col, num):
board[row][col] = num
if backtrack():
return True
board[row][col] = 0 # 回溯
return False # 1-9都不行，说明之前的选择有误
return True # 没有空格了，解决了
backtrack()
return board经典问题3：全排列
def permutations(nums):
"""生成所有排列"""
result = []
def backtrack(path, remaining):
if not remaining:
result.append(path[:])
return
for i in range(len(remaining)):
path.append(remaining[i])
backtrack(path, remaining[:i] + remaining[i + 1:])
path.pop() # 回溯
backtrack([], nums)
return result
print(permutations([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]经典问题4：子集生成
def subsets(nums):
"""生成所有子集"""
result = []
def backtrack(start, current):
result.append(current[:])
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop() # 回溯
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]回溯法的通用模板
def backtrack_template(candidates, path, result):
"""回溯法通用模板"""
if 满足结束条件:
result.append(path[:]) # 收集结果
return
for choice in 当前可选列表:
if 不满足约束条件:
continue # 剪枝
path.append(choice) # 做选择
backtrack_template(...) # 递归探索
path.pop() # 撤销选择（回溯）⚠️ 常见误区
- 误区1：“动态规划能解决所有优化问题” —— 动态规划需要满足两个条件：最优子结构和重叠子问题。如果子问题之间不重叠，用分治法更合适；如果没有最优子结构，可能需要回溯法穷举。
- 误区2：“贪心算法很简单” —— 贪心的代码通常很简单，但证明贪心的正确性往往很困难。很多看似适合贪心的问题，实际上贪心会给出错误答案。
- 误区3：“回溯法就是暴力穷举” —— 回溯法通过剪枝可以大大减少搜索空间。一个好的剪枝策略可能把指数级的搜索空间缩减到多项式级别。
五、三种算法思想的对比
| 特性 | 动态规划 | 贪心 | 回溯 |
|---|---|---|---|
| 核心策略 | 记住子问题答案 | 每步选最优 | 尝试所有可能 |
| 搜索范围 | 所有子问题 | 每步只看一个 | 所有分支（含剪枝） |
| 最优性保证 | 有（若满足条件） | 有时有有时没有 | 有（搜索完全的话） |
| 时间复杂度 | 多项式级 | 通常较低 | 可能指数级 |
| 适用场景 | 最优子结构+重叠子问题 | 贪心选择性质 | 组合搜索问题 |
| 典型问题 | 背包、LCS、编辑距离 | 活动选择、找零、哈夫曼 | N皇后、数独、全排列 |
一个选择指南：
- 先看问题有没有贪心选择性质——如果有，用贪心（最快）
- 再看是不是最优化问题且有重叠子问题——如果是，用动态规划
- 如果以上都不适用，或者需要穷举所有方案——用回溯
六、综合实战——股票买卖问题
这个问题完美展示了三种思想的应用。
# 版本1：只能买卖一次——贪心
def max_profit_once(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
print(max_profit_once([7, 1, 5, 3, 6, 4])) # 5（1买入，6卖出）
# 版本2：可以无限次买卖——贪心
def max_profit_unlimited(prices):
"""无限次买卖的最大利润"""
total = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
total += prices[i] - prices[i - 1] # 贪心：只要涨就赚
return total
print(max_profit_unlimited([7, 1, 5, 3, 6, 4])) # 7
# 版本3：最多买卖k次——动态规划
def max_profit_k_times(prices, k):
"""最多k次买卖的最大利润"""
n = len(prices)
if n < 2:
return 0
# dp[t][0] = 第t次交易完成后不持股的最大利润
# dp[t][1] = 第t次交易中持股的最大利润
dp = [[0, float('-inf')] for _ in range(k + 1)]
for price in prices:
for t in range(1, k + 1):
dp[t][0] = max(dp[t][0], dp[t][1] + price) # 卖出
dp[t][1] = max(dp[t][1], dp[t - 1][0] - price) # 买入
return dp[k][0]
print(max_profit_k_times([3, 2, 6, 5, 0, 3], 2)) # 7📝 掌握度自测
- 概念题： 动态规划和分治法都是把大问题拆成小问题，它们的核心区别是什么？
- 编码题： 用动态规划解决”最长递增子序列”问题。给定数组 [10, 9, 2, 5, 3, 7, 101, 18]，找出最长的严格递增子序列的长度。
- 分析题： 找零钱问题中，面值为 [1, 5, 11] 的硬币，凑出15元。贪心策略（先用最大面值）给出的答案是什么？最优答案是什么？为什么贪心失败了？
- 编码题： 用回溯法解决”组合总和”问题：给定数组 [2, 3, 6, 7] 和目标值 7，找出所有和为 7 的组合（数字可以重复使用）。
- 综合题： 你面对一个新的算法问题时，如何判断应该用动态规划、贪心还是回溯？列出你的判断思路。
💡 自我评估
- 全部答对：恭喜，你已经掌握了算法设计的三大核心武器。去刷题平台大展身手吧。
- 答对3-4题：非常不错，对于答错的题，建议回到对应的经典问题重新理解。
- 答对1-2题：这三种算法思想确实是最难的部分。建议挑一种（比如动态规划）深入练习，做到完全掌握后再学另外两种。
- 全部答错：这是正常的。这一章涵盖的内容通常需要数周到数月的练习才能真正掌握。建议从爬楼梯问题和全排列问题开始，反复练习直到形成肌肉记忆。
学了这么多数据结构和算法思想，你可能会问：面试的时候到底怎么用？刷题到底该怎么刷？下一章是一篇实战指南——不讲新知识，只讲如何把前面学到的一切变成你的面试实战能力。
购买课程解锁全部内容
刷题到通关：数据结构与算法面试实战
¥29.90