第16章 算法设计策略
16.1 引言
解决复杂问题时，直接堆砌代码往往事倍功半——面对“如何求最长公共子序列”“如何安排活动使参与人数最多”这类问题，缺乏通用思路的话，很容易陷入“暴力尝试-超时-优化-再超时”的循环。算法设计策略是前人从大量实践中总结的通用解题框架，它们不依赖具体问题细节，而是通过对问题的抽象拆解、子问题关联或搜索优化，将复杂问题转化为可解决的形式。
本章聚焦五种核心策略：分治法（将问题拆分为独立子问题）、动态规划（利用子问题重叠性优化递归）、贪心算法（通过局部最优实现全局最优）、回溯法（深度优先搜索+剪枝）、分支限界法（广度优先搜索+优先级）。每种策略将从“核心思想”“适用场景”“典型案例”三个维度展开，结合具体问题讲解“如何想到用这种策略”“如何落地实现”，帮助读者建立“策略-问题”的映射思维。
16.2 分治法
16.2.1 核心思想
分治法（Divide and Conquer）的字面意思就是“分而治之”：将一个复杂问题分解为若干个规模较小、结构与原问题相似的独立子问题，递归解决子问题后，将子问题的解合并得到原问题的解。
它的适用条件有三个：
1.可分解：问题能拆分为多个规模较小的子问题；
2.子问题独立：子问题的求解互不干扰（这点与动态规划不同）；
3.合并可解：子问题的解能通过某种规则合并为原问题的解。
日常最熟悉的分治法例子是归并排序：将数组分为左右两半（分解），递归排序两半（解决），最后合并两个有序子数组（合并）。下面通过一个更直观的例子理解分治法的完整流程。
16.2.2 案例：汉诺塔问题
问题描述
有3根柱子（A、B、C）和n个大小不同的圆盘，初始时所有圆盘按从小到大叠在A柱上。要求将所有圆盘移到C柱，每次只能移动一个圆盘，且大盘不能放在小盘上。如何设计移动步骤？
分治法思路
分解：要将n个圆盘从A移到C，需先将上面n-1个圆盘从A移到B（借助C），再将第n个圆盘从A移到C，最后将n-1个圆盘从B移到C（借助A）；
解决：递归移动n-1个圆盘（子问题与原问题结构相同，规模减小）；
合并：子问题的解（n-1个圆盘的移动步骤）与第n个圆盘的移动步骤组合，即为原问题的解。
代码实现
python

	def hanoi(n, source, auxiliary, target): 
	""" 
	分治法解决汉诺塔问题 
	:param n: 圆盘数量 
	:param source: 源柱子 
	:param auxiliary: 辅助柱子 
	:param target: 目标柱子 
	:return: 移动步骤列表 
	""" 
	steps = [] 
	if n == 1: 
	# 基本情况：1个圆盘直接从源柱移到目标柱 
	steps.append(f"Move disk 1 from {source} to {target}") 
	else: 
	# 步骤1：将n-1个圆盘从源柱移到辅助柱（借助目标柱） 
	steps += hanoi(n-1, source, target, auxiliary) 
	# 步骤2：将第n个圆盘从源柱移到目标柱 
	steps.append(f"Move disk {n} from {source} to {target}") 
	# 步骤3：将n-1个圆盘从辅助柱移到目标柱（借助源柱） 
	steps += hanoi(n-1, auxiliary, source, target) 
	return steps 
	
	# 测试：3个圆盘，从A移到C，借助B 
	print("
".join(hanoi(3, 'A', 'B', 'C')))

输出（共7步，符合2ⁿ-1的规律）：

	Move disk 1 from A to C 
	Move disk 2 from A to B 
	Move disk 1 from C to B 
	Move disk 3 from A to C 
	Move disk 1 from B to A 
	Move disk 2 from B to C 
	Move disk 1 from A to C

性能分析
时间复杂度：设移动n个圆盘的步骤数为T(n)，则T(n) = 2T(n-1) + 1，递归解得T(n) = 2ⁿ - 1，时间复杂度O(2ⁿ)（指数级，因问题本身复杂度决定）；
空间复杂度：递归栈深度为n，空间复杂度O(n)。
适用场景
分治法适合子问题独立且结构重复的问题，例如：
排序（归并、快速排序）；
查找（二分查找）；
矩阵运算（Strassen矩阵乘法）；
组合问题（汉诺塔、全排列）。
16.3 动态规划
16.3.1 核心思想
动态规划（Dynamic Programming, DP）与分治法类似，都是通过分解子问题解决原问题，但它针对的是子问题重叠（不同子问题包含相同的更小子问题）的场景。此时直接递归会导致大量重复计算，动态规划通过存储子问题的解（即“记忆化”）避免冗余，从而优化效率。
动态规划的核心要素：
最优子结构：原问题的最优解包含子问题的最优解；
重叠子问题：子问题重复出现，可存储解复用；
状态转移方程：用子问题的解表示原问题的解（核心）。
最经典的例子是斐波那契数列——递归解法会重复计算大量子问题，而动态规划通过存储中间结果将时间复杂度从O(2ⁿ)降至O(n)。
16.3.2 案例1：斐波那契数列（重叠子问题优化）
问题描述
求第n个斐波那契数（定义：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)）。
动态规划思路
状态定义：dp[i]表示第i个斐波那契数；
状态转移方程：dp[i] = dp[i-1] + dp[i-2]；
初始条件：dp[0]=0, dp[1]=1；
计算顺序：从i=2到n依次计算（自底向上）。
代码实现（对比递归与动态规划）
python

	# 递归解法（重叠子问题，效率低） 
	def fib_recursive(n): 
	if n <= 1: 
	return n 
	return fib_recursive(n-1) + fib_recursive(n-2) # 重复计算F(n-2)等 
	
	# 动态规划解法（自底向上，存储子问题解） 
	def fib_dp(n): 
	if n <= 1: 
	return n 
	dp = [0] * (n+1) # dp[i]存储第i个斐波那契数 
	dp[0], dp[1] = 0, 1 
	for i in range(2, n+1): 
	dp[i] = dp[i-1] + dp[i-2] # 复用子问题解 
	return dp[n] 
	
	# 测试：计算第10个斐波那契数（正确结果55） 
	print(fib_dp(10)) # 输出55

性能对比：
递归解法：时间复杂度O(2ⁿ)（指数级，n=30时已明显卡顿）；
动态规划：时间复杂度O(n)，空间复杂度O(n)（可优化至O(1)，因只需存储前两个数）。
16.3.3 案例2：最长公共子序列（LCS，最优子结构）
问题描述
给定两个字符串s1和s2，求它们的最长公共子序列（子序列可不连续，如“ABCBDAB”与“BDCAB”的LCS是“BCAB”，长度4）。
动态规划思路
状态定义：dp[i][j]表示s1[0..i-1]与s2[0..j-1]的LCS长度；
状态转移方程：
o若s1[i-1] == s2[j-1]（当前字符相同），则dp[i][j] = dp[i-1][j-1] + 1；
o否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])（取去掉s1[i-1]或s2[j-1]后的LCS最大值）；
初始条件：dp[0][j] = 0, dp[i][0] = 0（空字符串与任何字符串的LCS长度为0）。
代码实现
python

	def lcs(s1, s2): 
	"""动态规划求最长公共子序列长度及序列""" 
	m, n = len(s1), len(s2) 
	# 创建dp表，dp[i][j]存储s1[0..i-1]与s2[0..j-1]的LCS长度 
	dp = [[0]*(n+1) for _ in range(m+1)] 
	
	# 填充dp表（自底向上） 
	for i in range(1, m+1): 
	for j in range(1, n+1): 
	if s1[i-1] == s2[j-1]: 
	dp[i][j] = dp[i-1][j-1] + 1 
	else: 
	dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
	
	# 回溯dp表，获取LCS序列 
	i, j = m, n 
	lcs_str = [] 
	while i > 0 and j > 0: 
	if s1[i-1] == s2[j-1]: 
	lcs_str.append(s1[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_str)) # 反转得到正序LCS 
	
	# 测试 
	length, sequence = lcs("ABCBDAB", "BDCAB") 
	print(f"LCS长度：{length}，序列：{sequence}") # 输出：LCS长度：4，序列：BCAB

性能分析
时间复杂度：O(mn)（m、n为两字符串长度，需填充m×n的dp表）；
空间复杂度：O(mn)（存储dp表），可优化为O(min(m,n))（仅存储当前行和上一行）。
16.3.4 适用场景
动态规划适合有重叠子问题和最优子结构的问题，例如：
优化问题（最长公共子序列、最短路径、背包问题）；
计数问题（不同路径数量、编辑距离）；
决策问题（打家劫舍、股票买卖）。
16.4 贪心算法
16.4.1 核心思想
贪心算法（Greedy Algorithm）通过在每一步选择局部最优解，希望最终得到全局最优解。它与动态规划的区别在于：动态规划需考虑所有子问题的解并选择最优，而贪心算法仅根据当前信息做选择，不回溯（即“目光短浅”但高效）。
贪心算法的关键是贪心选择性质：局部最优的选择能导致全局最优。但并非所有问题都满足这一性质，例如“零钱兑换”问题——用1、5、10元硬币凑27元，贪心策略（每次选最大面额）会选10+10+5+1+1（5枚），而最优解是10+5+5+5+1+1（6枚？不，其实27=10+10+5+1+1是5枚，已经是最优，这里可能例子不对，正确反例是用25、10、5、1凑30，贪心选25+5（2枚），是最优；若硬币是1、3、4，凑6，贪心选4+1+1（3枚），而最优是3+3（2枚），此时贪心失效）。
16.4.2 案例1：活动选择问题（贪心有效）
问题描述
有n个活动，每个活动有开始时间s[i]和结束时间f[i]，同一时间只能参加一个活动，如何选择最多的活动？
贪心策略
选择最早结束的活动：结束时间早，剩余时间能容纳更多活动。步骤：
1.按结束时间排序活动；
2.选择第一个活动，然后依次选择与上一个活动不冲突（开始时间≥上一个结束时间）的最早结束活动。
代码实现
python

	def activity_selection(activities): 
	""" 
	贪心算法选择最多活动 
	:param activities: 活动列表，每个元素为(s, f)，s是开始时间，f是结束时间 
	:return: 选中的活动列表 
	""" 
	# 步骤1：按结束时间排序 
	sorted_activities = sorted(activities, key=lambda x: x[1]) 
	selected = [] 
	last_end = -1 # 上一个活动的结束时间 
	
	# 步骤2：选择不冲突的最早结束活动 
	for s, f in sorted_activities: 
	if s >= last_end: # 当前活动开始时间≥上一个结束时间，不冲突 
	selected.append((s, f)) 
	last_end = f 
	return selected 
	
	# 测试：活动列表[(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)] 
	activities = [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)] 
	selected = activity_selection(activities) 
	print(f"最多可参加{len(selected)}个活动：{selected}") 
	# 输出：最多可参加4个活动：[(1,4), (5,7), (8,11), (12,16)]

16.4.3 案例2：哈夫曼编码（贪心有效）
问题描述
哈夫曼编码是一种无损压缩算法，通过为高频字符分配短编码、低频字符分配长编码，减少总编码长度。例如字符A(5次)、B(9次)、C(12次)、D(13次)、E(16次)、F(45次)，如何设计编码？
贪心策略
构建哈夫曼树：
1.将所有字符看作节点，权值为频率，组成森林；
2.每次选两个权值最小的节点，合并为一个新节点（权值为两节点之和）；
3.重复步骤2，直至森林只剩一棵树（哈夫曼树）；
4.从根到叶，左分支记0，右分支记1，路径即为字符编码。
代码实现（简化版）
python

	import heapq 
	
	class HuffmanNode: 
	def __init__(self, freq, char=None, left=None, right=None): 
	self.freq = freq # 频率 
	self.char = char # 字符（叶节点才有） 
	self.left = left 
	self.right = right 
	
	# 定义比较方法，用于优先队列（按频率从小到大） 
	def __lt__(self, other): 
	return self.freq < other.freq 
	
	def huffman_coding(freq_dict): 
	"""哈夫曼编码：返回字符-编码映射""" 
	# 步骤1：创建叶节点优先队列（最小堆） 
	heap = [HuffmanNode(freq, char) for char, freq in freq_dict.items()] 
	heapq.heapify(heap) 
	
	# 步骤2：合并节点构建哈夫曼树 
	while len(heap) > 1: 
	left = heapq.heappop(heap) # 最小频率节点 
	right = heapq.heappop(heap) # 次小频率节点 
	# 合并为新节点（无字符，频率为两者之和） 
	merged = HuffmanNode(left.freq + right.freq, left=left, right=right) 
	heapq.heappush(heap, merged) 
	
	# 步骤3：遍历哈夫曼树生成编码（递归） 
	code_dict = {} 
	def traverse(node, current_code=""): 
	if node.char: # 叶节点，记录编码 
	code_dict[node.char] = current_code if current_code else "0" # 若只有一个字符 
	return 
	traverse(node.left, current_code + "0") 
	traverse(node.right, current_code + "1") 
	
	if heap: # 处理空输入情况 
	traverse(heap[0]) 
	return code_dict 
	
	# 测试 
	freq = {'A':5, 'B':9, 'C':12, 'D':13, 'E':16, 'F':45} 
	codes = huffman_coding(freq) 
	print("哈夫曼编码：", codes) 
	# 输出（编码不唯一，但频率高的编码短）： 
	# 哈夫曼编码： {'F': '0', 'C': '100', 'D': '101', 'A': '1100', 'B': '1101', 'E': '111'}

16.4.4 适用场景
贪心算法适合满足贪心选择性质的问题，例如：
资源分配（活动选择、区间覆盖）；
编码压缩（哈夫曼编码）；
图算法（最小生成树Kruskal算法、最短路径Dijkstra算法）；
调度问题（任务调度、会议安排）。
16.5 回溯法
16.5.1 核心思想
回溯法（Backtracking）是一种深度优先搜索（DFS）的暴力搜索方法，通过尝试所有可能的解，并在发现当前路径不可能得到有效解时剪枝（停止继续搜索该路径），从而避免无效计算。
回溯法的典型应用是组合优化问题（如N皇后、子集和、全排列），其解题框架可概括为：
def backtrack(路径, 选择列表):

	if 满足结束条件: 
	记录路径 
	return 
	for 选择 in 选择列表: 
	做选择（加入路径） 
	backtrack(路径, 新选择列表) 
	撤销选择（回溯）

16.5.2 案例：N皇后问题
问题描述
在n×n的棋盘上放置n个皇后，使它们不能互相攻击（即任意两个皇后不在同一行、同一列或同一斜线上），求所有可能的放置方案。
回溯法思路
路径：已放置皇后的位置（行、列）；
选择列表：当前行可放置皇后的列（需排除与已有皇后冲突的列）；
结束条件：已放置n个皇后（行数= n）；
剪枝条件：新放置的皇后与已有皇后不冲突（同一列、同一斜线）。
代码实现
python

	def solve_n_queens(n): 
	"""回溯法解决N皇后问题，返回所有放置方案""" 
	def is_valid(row, col, queens): 
	"""判断(row, col)是否可放置皇后（与已有queens不冲突）""" 
	for r, c in queens: 
	# 同一列或同一斜线（行差=列差） 
	if c == col or abs(row - r) == abs(col - c): 
	return False 
	return True 
	
	def backtrack(row, queens, path, result): 
	if row == n: 
	# 记录方案：将列号转换为字符串（如[1,3,0,2]→[".Q..","...Q","Q...","..Q."]） 
	board = ['.'*col + 'Q' + '.'*(n-col-1) for _, col in queens] 
	result.append(board) 
	return 
	for col in range(n): 
	if is_valid(row, col, queens): 
	# 做选择 
	queens.append((row, col)) 
	backtrack(row+1, queens, path, result) 
	# 撤销选择（回溯） 
	queens.pop() 
	
	result = [] 
	backtrack(0, [], [], result) 
	return result 
	
	# 测试：4皇后 
	solutions = solve_n_queens(4) 
	for i, sol in enumerate(solutions): 
	print(f"方案{i+1}：") 
	for row in sol: 
	print(row) 
	print()

输出（4皇后有2种方案）：
方案1：

	.Q.. 
	...Q 
	Q... 
	..Q. 
	
	方案2： 
	..Q. 
	Q... 
	...Q 
	.Q..

性能分析
时间复杂度：O(n!)（n皇后问题的解数量约为n!/(2n)，回溯法需遍历所有可能解）；
空间复杂度：O(n)（递归栈深度为n，存储当前皇后位置）。
16.5.3 适用场景
回溯法适合解空间较大但可通过剪枝优化的问题，例如：
组合问题（子集、组合总和、全排列）；
约束满足问题（N皇后、数独）；
路径搜索（迷宫问题、单词搜索）。
16.6 分支限界法
16.6.1 核心思想
分支限界法（Branch and Bound）与回溯法类似，都是搜索解空间，但它采用广度优先搜索（BFS）或优先级队列（如最小/最大堆），并通过限界函数（估算当前路径的最优可能解）剪去不可能得到最优解的分支。
分支限界法通常用于求解最优解（如旅行商问题求最短路径），而回溯法更常用于求所有可行解。
16.6.2 案例：旅行商问题（TSP）
问题描述
旅行商从城市0出发，访问所有城市恰好一次后返回出发城市，求最短路径（假设城市间距离已知）。
分支限界法思路
解空间：所有可能的城市排列（路径）；
优先级队列：按当前路径长度+未访问城市的最小距离下界（限界）排序，优先扩展“最可能是最优解”的路径；
限界函数：当前路径长度 + 剩余城市的最小生成树（MST）下界（估算完成剩余路径的最小距离），若该下界≥当前最优解，则剪枝。
代码实现（简化版，基于优先级队列）
python

	import heapq 
	
	def tsp(city_distances): 
	"""分支限界法求解旅行商问题（求最短路径）""" 
	n = len(city_distances) 
	if n == 0: 
	return 0, [] 
	# 初始状态：(当前路径长度, 当前城市, 已访问城市集合, 路径) 
	# 优先级队列按（当前长度+下界, 当前长度, 当前城市, 已访问, 路径）排序 
	heap = [] 
	# 初始下界：从城市0出发，访问所有城市的最小距离（简化为当前长度，实际需计算MST下界） 
	initial_path = [0] 
	initial_visited = frozenset([0]) 
	heapq.heappush(heap, (0, 0, 0, initial_visited, initial_path)) 
	
	min_distance = float('inf') 
	best_path = [] 
	
	while heap: 
	bound, current_dist, current_city, visited, path = heapq.heappop(heap) 
	
	# 若已访问所有城市，返回出发城市，更新最优解 
	if len(visited) == n: 
	total_dist = current_dist + city_distances[current_city][0] # 返回出发城市 
	if total_dist < min_distance: 
	min_distance = total_dist 
	best_path = path + [0] 
	continue 
	
	# 若当前下界≥已知最优解，剪枝 
	if bound >= min_distance: 
	continue 
	
	# 扩展下一个城市 
	for next_city in range(n): 
	if next_city not in visited: 
	new_visited = frozenset(visited | {next_city}) 
	new_dist = current_dist + city_distances[current_city][next_city] 
	new_path = path + [next_city] 
	# 简化下界：当前距离 + 剩余城市的最小距离之和（实际应计算MST下界） 
	new_bound = new_dist + sum(min(city_distances[city][next_city] for next_city in range(n) if next_city not in new_visited) for city in new_visited) 
	heapq.heappush(heap, (new_bound, new_dist, next_city, new_visited, new_path)) 
	
	return min_distance, best_path 
	
	# 测试：4个城市的距离矩阵（城市0-3） 
	distances = [ 
	[0, 10, 15, 20], 
	[10, 0, 35, 25], 
	[15, 35, 0, 30], 
	[20, 25, 30, 0] 
	] 
	min_dist, path = tsp(distances) 
	print(f"最短路径：{path}，距离：{min_dist}") # 输出：最短路径：[0, 1, 3, 2, 0]，距离：80（0→1→3→2→0：10+25+30+15=80）

16.6.3 适用场景
分支限界法适合求解最优解且解空间较大的问题，例如：
旅行商问题（TSP）；
背包问题（0-1背包求最大价值）；
整数规划问题；
电路设计（最小成本电路）。
16.7 本章总结
算法设计策略是解决复杂问题的“思维框架”，本章介绍的五种策略各有侧重：
分治法：分解独立子问题，合并解（如汉诺塔、归并排序）；
动态规划：存储重叠子问题的解，通过最优子结构求全局最优（如LCS、背包问题）；
贪心算法：局部最优选择导致全局最优，高效但依赖问题性质（如活动选择、哈夫曼编码）；
回溯法：深度优先搜索+剪枝，适合求所有可行解（如N皇后、子集和）；
分支限界法：广度优先/优先级搜索+限界剪枝，适合求最优解（如TSP）。
选择策略时需考虑问题特性：是否有重叠子问题（动态规划）、是否满足贪心选择性质（贪心）、是否需要所有解（回溯）或仅最优解（分支限界）。实际问题中，多种策略可能结合使用（如动态规划+贪心、回溯+分支限界），关键是理解每种策略的核心思想，而非死记硬背算法步骤。
16.8 思考题
1.用动态规划解决“编辑距离”问题（计算将一个字符串转换为另一个的最少操作次数，操作包括插入、删除、替换）。
2.证明贪心算法在“活动选择问题”中能得到最优解（提示：反证法，假设存在全局最优解不包含贪心选择的第一个活动，推出矛盾）。
3.用回溯法解决“子集和”问题（给定数组和目标和，找出所有和为目标的子集），并添加剪枝条件（如当前和>目标和时停止搜索）。
4.对比动态规划和分支限界法在“0-1背包问题”中的应用，分析时间复杂度差异。
5.设计一个算法，用最少的硬币兑换一定金额，硬币面额不固定（需判断问题是否满足贪心选择性质，若不满足则用动态规划）。
第16章 算法设计策略
16.1 引言
在解决复杂问题时，仅掌握数据结构（如数组、树、图）和基础算法（如排序、查找）往往不足以高效应对。算法设计策略是从问题本质出发，通过抽象、分解、优化等思路将复杂问题转化为可解形式的通用框架。它们不依赖具体数据结构，而是提供一种“解题思路”，帮助开发者在面对未知问题时快速找到突破口。
本章聚焦五种工程中最常用的算法设计策略：分治法（Divide and Conquer）、动态规划（Dynamic Programming）、贪心算法（Greedy Algorithm）、回溯法（Backtracking）和分支限界法（Branch and Bound）。每种策略将从核心思想、适用场景、典型案例（含Python实现）和性能分析四个维度展开，注重底层逻辑与工程实践的结合，帮助读者建立“问题-策略”的映射思维。
16.2 分治法
16.2.1 核心思想
分治法的本质是“分而治之”，即将一个规模为 n n n 的复杂问题分解为 k k k 个规模较小的独立子问题（通常 k=2 k=2 k=2，即二分），递归求解子问题后，通过合并子问题的解得到原问题的解。其流程可概括为：
1.分解（Divide）：将原问题分解为若干个与原问题结构相同、规模较小的子问题；
2.解决（Conquer）：若子问题规模足够小，则直接求解；否则递归求解子问题；
3.合并（Combine）：将子问题的解合并为原问题的解。
分治法与递归紧密相关，但并非所有递归问题都是分治法——关键在于子问题是否独立且可合并。例如，斐波那契数列的递归求解虽分解为子问题，但子问题重叠（非独立），不属于分治法；而归并排序的左右子数组排序独立，属于典型分治法。
16.2.2 典型案例：汉诺塔问题
问题描述
有3根柱子（A、B、C）和 n n n 个大小不同的圆盘，初始时所有圆盘按从小到大叠放在A柱上。要求将所有圆盘移到C柱，每次只能移动一个圆盘，且大盘不能放在小盘上。求所有移动步骤。
分治法应用
分解：
要将 n n n 个圆盘从A移到C，需先将上方 n−1 n-1 n−1 个圆盘从A移到B（借助C）；
再将第 n n n 个圆盘从A移到C；
最后将 n−1 n-1 n−1 个圆盘从B移到C（借助A）。
解决：
递归移动 n−1 n-1 n−1 个圆盘（子问题与原问题结构相同，规模减小）。
合并：
将“移动 n−1 n-1 n−1 个圆盘到B”“移动第 n n n 个圆盘到C”“移动 n−1 n-1 n−1 个圆盘到C”三个步骤的移动序列组合，即为原问题的解。
代码实现
python

	def hanoi(n, source, auxiliary, target): 
	""" 
	分治法求解汉诺塔问题 
	:param n: 圆盘数量 
	:param source: 源柱子（初始圆盘所在柱） 
	:param auxiliary: 辅助柱子 
	:param target: 目标柱子（最终圆盘所在柱） 
	:return: 移动步骤列表，每个元素为"Move disk X from A to B"格式 
	""" 
	steps = [] 
	if n == 1: 
	# 基本情况：1个圆盘直接移动 
	steps.append(f"Move disk 1 from {source} to {target}") 
	else: 
	# 步骤1：将n-1个圆盘从源柱移到辅助柱（借助目标柱） 
	steps += hanoi(n-1, source, target, auxiliary) 
	# 步骤2：将第n个圆盘从源柱移到目标柱 
	steps.append(f"Move disk {n} from {source} to {target}") 
	# 步骤3：将n-1个圆盘从辅助柱移到目标柱（借助源柱） 
	steps += hanoi(n-1, auxiliary, source, target) 
	return steps 
	
	# 测试：3个圆盘，从A柱移到C柱，辅助柱为B 
	if __name__ == "__main__": 
	n = 3 
	steps = hanoi(n, 'A', 'B', 'C') 
	print(f"{n}个圆盘的汉诺塔移动步骤（共{len(steps)}步）：") 
	for i, step in enumerate(steps, 1): 
	print(f"{i}. {step}")

输出：
3个圆盘的汉诺塔移动步骤（共7步）：

	1. Move disk 1 from A to C 
	2. Move disk 2 from A to B 
	3. Move disk 1 from C to B 
	4. Move disk 3 from A to C 
	5. Move disk 1 from B to A 
	6. Move disk 2 from B to C 
	7. Move disk 1 from A to C

性能分析
时间复杂度：设移动 n n n 个圆盘的步骤数为 T(n) T(n) T(n)，则 T(n)=2T(n−1)+1 T(n) = 2T(n-1) + 1 T(n)=2T(n−1)+1（递归式），初始条件 T(1)=1 T(1)=1 T(1)=1。解得 T(n)=2n−1 T(n) = 2^n - 1 T(n)=2n−1，时间复杂度 O(2n) O(2^n) O(2n)（指数级，由问题本身的递归结构决定）。
空间复杂度：递归栈深度为 n n n，空间复杂度 O(n) O(n) O(n)。
16.2.3 适用场景
分治法适用于子问题独立且可合并的问题，典型应用包括：
排序（归并排序、快速排序）；
查找（二分查找）；
组合问题（汉诺塔、全排列）；
矩阵运算（Strassen矩阵乘法）。
16.3 动态规划
16.3.1 核心思想
动态规划（DP）针对子问题重叠的场景，通过存储子问题的解（即“记忆化”）避免重复计算，从而优化递归效率。其核心要素包括：
重叠子问题：不同子问题包含相同的更小子问题（与分治法的“独立子问题”不同）；
最优子结构：原问题的最优解包含子问题的最优解；
状态转移方程：用子问题的解表示原问题的解（核心）。
动态规划的实现方式有两种：
自顶向下（记忆化递归）：递归求解子问题，存储已计算的子问题解；
自底向上（迭代填表）：从最小子问题开始，按顺序计算并存储解，直至原问题。
16.3.2 典型案例1：斐波那契数列（重叠子问题优化）
问题描述
求第 n n n 个斐波那契数（定义：F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2) F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) F(0)=0,F(1)=1,F(n)=F(n−1)+F(n−2)）。
动态规划应用
重叠子问题：
递归求解 F(n) F(n) F(n) 时，F(n−2) F(n-2) F(n−2) 会被 F(n−1) F(n-1) F(n−1) 和 F(n) F(n) F(n) 重复计算，子问题重叠严重。
自底向上优化：
定义状态 dp[i]=F(i) dp[i] = F(i) dp[i]=F(i)，状态转移方程 dp[i]=dp[i−1]+dp[i−2] dp[i] = dp[i-1] + dp[i-2] dp[i]=dp[i−1]+dp[i−2]，从 i=2 i=2 i=2 迭代计算至 i=n i=n i=n。
代码实现
python

	def fibonacci_dp(n): 
	"""自底向上动态规划求解斐波那契数列""" 
	if n <= 1: 
	return n 
	# 初始化dp表，存储子问题解 
	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] 
	
	# 测试 
	print(fibonacci_dp(10)) # 输出：55

性能分析
时间复杂度：O(n) O(n) O(n)（迭代 n−1 n-1 n−1 次）；
空间复杂度：O(n) O(n) O(n)（可优化至 O(1) O(1) O(1)，因仅需存储前两个状态）。
16.3.3 典型案例2：最长公共子序列（LCS，最优子结构）
问题描述
给定两个字符串 s1 s1 s1 和 s2 s2 s2，求它们的最长公共子序列（子序列可不连续，如“ABCBDAB”与“BDCAB”的LCS为“BCAB”，长度4）。
动态规划应用
状态定义：
设 dp[i][j] dp[i][j] dp[i][j] 表示 s1[0..i−1] s1[0..i-1] s1[0..i−1] 与 s2[0..j−1] s2[0..j-1] s2[0..j−1] 的LCS长度。
状态转移方程：
若 s1[i−1]s2[j−1] s1[i-1] == s2[j-1] s1[i−1]s2[j−1]（当前字符相同），则 dp[i][j]=dp[i−1][j−1]+1 dp[i][j] = dp[i-1][j-1] + 1 dp[i][j]=dp[i−1][j−1]+1（LCS长度+1）；
否则，dp[i][j]=max⁡(dp[i−1][j],dp[i][j−1]) dp[i][j] = max(dp[i-1][j], dp[i][j-1]) dp[i][j]=max(dp[i−1][j],dp[i][j−1])（取去掉 s1[i−1] s1[i-1] s1[i−1] 或 s2[j−1] s2[j-1] s2[j−1] 后的LCS最大值）。
初始条件：
dp[0][j]=0 dp[0][j] = 0 dp[0][j]=0（空字符串与任何字符串的LCS长度为0），dp[i][0]=0 dp[i][0] = 0 dp[i][0]=0。
代码实现
python

	def lcs(s1, s2): 
	""" 
	自底向上动态规划求最长公共子序列 
	:return: (LCS长度, LCS序列) 
	""" 
	m, n = len(s1), len(s2) 
	# 初始化dp表（(m+1)×(n+1)） 
	dp = [[0] * (n + 1) for _ in range(m + 1)] 
	
	# 填充dp表 
	for i in range(1, m + 1): 
	for j in range(1, n + 1): 
	if s1[i-1] == s2[j-1]: 
	dp[i][j] = dp[i-1][j-1] + 1 
	else: 
	dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
	
	# 回溯dp表获取LCS序列 
	i, j = m, n 
	lcs_seq = [] 
	while i > 0 and j > 0: 
	if s1[i-1] == s2[j-1]: 
	lcs_seq.append(s1[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_seq)) # 反转得到正序序列 
	
	# 测试 
	length, seq = lcs("ABCBDAB", "BDCAB") 
	print(f"LCS长度：{length}，序列：{seq}") # 输出：LCS长度：4，序列：BCAB

性能分析
时间复杂度：O(mn) O(mn) O(mn)（m,n m,n m,n 为字符串长度，需填充 (m+1)(n+1) (m+1)(n+1) (m+1)(n+1) 的dp表）；
空间复杂度：O(mn) O(mn) O(mn)（存储dp表，可优化至 O(min⁡(m,n)) O(min(m,n)) O(min(m,n))）。
16.3.4 适用场景
动态规划适用于有重叠子问题和最优子结构的问题，典型应用包括：
优化问题（LCS、最短路径、背包问题）；
计数问题（不同路径数量、编辑距离）；
决策问题（打家劫舍、股票买卖）。
16.4 贪心算法
16.4.1 核心思想
贪心算法通过每一步选择局部最优解，期望最终得到全局最优解。其关键是贪心选择性质：局部最优选择能导致全局最优。与动态规划相比，贪心算法不依赖子问题的解，而是直接根据当前信息做选择，且不回溯（“不可逆”）。
注意：并非所有问题都满足贪心选择性质。例如，“零钱兑换”问题（用1、3、4元硬币凑6元），贪心策略（选最大面额4+1+1=6，3枚）并非最优（3+3=6，2枚），此时贪心失效，需用动态规划。
16.4.2 典型案例1：活动选择问题
问题描述
有 n n n 个活动，每个活动有开始时间 s[i] s[i] s[i] 和结束时间 f[i] f[i] f[i]，同一时间只能参加一个活动，如何选择最多的活动？
贪心策略
选择最早结束的活动：结束时间早，剩余时间可容纳更多活动。步骤：
1.按结束时间排序活动；
2.选择第一个活动，然后依次选择与上一个活动不冲突（开始时间≥上一个结束时间）的最早结束活动。
代码实现
python

	def activity_selection(activities): 
	""" 
	贪心选择最多活动 
	:param activities: 活动列表，元素为(s, f)，s开始时间，f结束时间 
	:return: 选中的活动列表 
	""" 
	# 步骤1：按结束时间排序 
	sorted_acts = sorted(activities, key=lambda x: x[1]) 
	selected = [] 
	last_end = -1 # 上一个活动的结束时间 
	
	# 步骤2：选择不冲突的最早结束活动 
	for s, f in sorted_acts: 
	if s >= last_end: 
	selected.append((s, f)) 
	last_end = f 
	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)] 
	selected = activity_selection(activities) 
	print(f"最多可参加{len(selected)}个活动：{selected}") 
	# 输出：最多可参加4个活动：[(1, 4), (5, 7), (8, 11), (12, 16)]

性能分析
时间复杂度：O(nlog⁡n) O(n log n) O(nlogn)（主要耗时在排序）；
空间复杂度：O(1) O(1) O(1)（若允许修改原列表，排序可原地进行）。
16.4.3 典型案例2：哈夫曼编码
问题描述
哈夫曼编码是一种无损压缩算法，通过为高频字符分配短编码、低频字符分配长编码，减少总编码长度。例如，字符频率为 A:5,B:9,C:12,D:13,E:16,F:45 A:5, B:9, C:12, D:13, E:16, F:45 A:5,B:9,C:12,D:13,E:16,F:45，如何设计编码？
贪心策略
构建哈夫曼树：
1.将所有字符视为节点，权值为频率，组成森林；
2.每次选择两个权值最小的节点，合并为一个新节点（权值为两节点之和）；
3.重复步骤2，直至森林只剩一棵树（哈夫曼树）；
4.从根到叶，左分支记“0”，右分支记“1”，路径即为字符编码。
代码实现
python

	import heapq 
	
	class HuffmanNode: 
	def __init__(self, freq, char=None, left=None, right=None): 
	self.freq = freq # 频率 
	self.char = char # 字符（叶节点才有） 
	self.left = left 
	self.right = right 
	
	def __lt__(self, other): # 用于优先队列比较 
	return self.freq < other.freq 
	
	def huffman_coding(freq_dict): 
	""" 
	构建哈夫曼树并生成编码 
	:param freq_dict: 字符-频率字典 
	:return: 字符-编码字典 
	""" 
	# 步骤1：构建叶节点优先队列（最小堆） 
	heap = [HuffmanNode(freq, char) for char, freq in freq_dict.items()] 
	heapq.heapify(heap) 
	
	# 步骤2：合并节点构建哈夫曼树 
	while len(heap) > 1: 
	left = heapq.heappop(heap) # 最小频率节点 
	right = heapq.heappop(heap) # 次小频率节点 
	# 合并为新节点（无字符） 
	merged = HuffmanNode(left.freq + right.freq, left=left, right=right) 
	heapq.heappush(heap, merged) 
	
	# 步骤3：遍历哈夫曼树生成编码（递归） 
	code_dict = {} 
	def traverse(node, current_code=""): 
	if node.char: # 叶节点 
	code_dict[node.char] = current_code if current_code else "0" # 单节点情况 
	return 
	traverse(node.left, current_code + "0") 
	traverse(node.right, current_code + "1") 
	
	if heap: 
	traverse(heap[0]) 
	return code_dict 
	
	# 测试 
	freq = {'A':5, 'B':9, 'C':12, 'D':13, 'E':16, 'F':45} 
	codes = huffman_coding(freq) 
	print("哈夫曼编码：", codes) 
	# 输出（编码不唯一，但高频字符编码短）： 
	# 哈夫曼编码： {'F': '0', 'C': '100', 'D': '101', 'A': '1100', 'B': '1101', 'E': '111'}

性能分析
时间复杂度：O(nlog⁡n) O(n log n) O(nlogn)（n n n 为字符数，优先队列操作 O(nlog⁡n) O(n log n) O(nlogn)）；
空间复杂度：O(n) O(n) O(n)（存储哈夫曼树节点）。
16.4.4 适用场景
贪心算法适用于满足贪心选择性质的问题，典型应用包括：
资源分配（活动选择、区间覆盖）；
编码压缩（哈夫曼编码）；
图算法（最小生成树Kruskal算法、最短路径Dijkstra算法）；
调度问题（任务调度、会议安排）。
16.5 回溯法
16.5.1 核心思想
回溯法是一种深度优先搜索（DFS） 的暴力搜索方法，通过尝试所有可能的解，并在发现当前路径不可能得到有效解时剪枝（停止搜索该路径），从而避免无效计算。其解题框架可概括为：
python

	def backtrack(路径, 选择列表): 
	if 满足结束条件: 
	记录路径 
	return 
	for 选择 in 选择列表: 
	if 选择无效（剪枝条件）: 
	continue 
	做选择（加入路径） 
	backtrack(路径, 新选择列表) 
	撤销选择（回溯）

回溯法的本质是“穷举+剪枝”，适用于解空间较大但约束条件明确的问题（如组合、排列、约束满足问题）。
16.5.2 典型案例：N皇后问题
问题描述
在 n×n n imes n n×n 的棋盘上放置 n n n 个皇后，使它们不能互相攻击（任意两个皇后不在同一行、列或斜线），求所有放置方案。
回溯法应用
路径：已放置皇后的位置（行、列）；
选择列表：当前行可放置皇后的列（排除与已有皇后冲突的列）；
结束条件：已放置 n n n 个皇后（行数 = n n n）；
剪枝条件：新放置的皇后与已有皇后不在同一列或斜线。
代码实现
python

	def solve_n_queens(n): 
	""" 
	回溯法求解N皇后问题 
	:return: 所有方案的列表，每个方案为n×n的棋盘表示（'Q'表示皇后，'.'表示空位） 
	""" 
	def is_valid(row, col, queens): 
	"""判断(row, col)是否可放置皇后""" 
	for r, c in queens: 
	# 同一列或同一斜线（行差=列差） 
	if c == col or abs(row - r) == abs(col - c): 
	return False 
	return True 
	
	def backtrack(row, queens, path, result): 
	if row == n: 
	# 记录方案：将(行,列)转换为棋盘字符串 
	board = ['.'*col + 'Q' + '.'*(n-col-1) for _, col in queens] 
	result.append(board) 
	return 
	for col in range(n): 
	if is_valid(row, col, queens): 
	# 做选择 
	queens.append((row, col)) 
	backtrack(row + 1, queens, path, result) 
	# 撤销选择（回溯） 
	queens.pop() 
	
	result = [] 
	backtrack(0, [], [], result) 
	return result 
	
	# 测试：4皇后 
	solutions = solve_n_queens(4) 
	print(f"4皇后共有{len(solutions)}种方案：") 
	for i, sol in enumerate(solutions): 
	print(f"方案{i+1}：") 
	for row in sol: 
	print(row) 
	print()

输出：
4皇后共有2种方案：
方案1：

	.Q.. 
	...Q 
	Q... 
	..Q. 
	
	方案2： 
	..Q. 
	Q... 
	...Q 
	.Q..

性能分析
时间复杂度：O(n!) O(n!) O(n!)（n n n 皇后问题的解数量约为 n!/(2n) n!/(2n) n!/(2n)，回溯法需遍历所有可能解）；
空间复杂度：O(n) O(n) O(n)（递归栈深度为 n n n，存储当前皇后位置）。
16.5.3 适用场景
回溯法适用于解空间较大但可通过剪枝优化的问题，典型应用包括：
组合问题（子集、组合总和、全排列）；
约束满足问题（N皇后、数独）；
路径搜索（迷宫问题、单词搜索）。
16.6 分支限界法
16.6.1 核心思想
分支限界法与回溯法类似，均搜索解空间，但采用广度优先搜索（BFS） 或优先级队列（如最小/最大堆），并通过限界函数（估算当前路径的最优可能解）剪去不可能得到最优解的分支。
分支限界法主要用于求解最优解（如最短路径、最大价值），而回溯法更常用于求所有可行解。
16.6.2 典型案例：旅行商问题（TSP）
问题描述
旅行商从城市0出发，访问所有城市恰好一次后返回出发城市，求最短路径（假设城市间距离已知）。
分支限界法应用
解空间：所有可能的城市排列（路径）；
优先级队列：按“当前路径长度+剩余城市的最小距离下界”（限界值）排序，优先扩展“最可能是最优解”的路径；
限界函数：当前路径长度 + 剩余城市的最小生成树（MST）下界（估算完成剩余路径的最小距离）；
剪枝条件：当前路径的限界值 ≥ 当前最优解，则停止扩展该路径。
代码实现（简化版）
python

	import heapq 
	
	def tsp(city_distances): 
	""" 
	分支限界法求解旅行商问题（简化版，限界函数为当前距离+剩余城市最小距离之和） 
	:param city_distances: 城市间距离矩阵，city_distances[i][j]为城市i到j的距离 
	:return: (最短路径长度, 路径) 
	""" 
	n = len(city_distances) 
	if n == 0: 
	return (0, []) 
	
	# 初始化优先级队列：(限界值, 当前距离, 当前城市, 已访问城市, 路径) 
	heap = [] 
	initial_visited = frozenset([0]) # 从城市0出发 
	heapq.heappush(heap, (0, 0, 0, initial_visited, [0])) 
	
	min_distance = float('inf') 
	best_path = [] 
	
	while heap: 
	bound, current_dist, current_city, visited, path = heapq.heappop(heap) 
	
	# 若已访问所有城市，返回出发城市并更新最优解 
	if len(visited) == n: 
	total_dist = current_dist + city_distances[current_city][0] # 返回出发城市 
	if total_dist < min_distance: 
	min_distance = total_dist 
	best_path = path + [0] 
	continue 
	
	# 若当前限界≥已知最优解，剪枝 
	if bound >= min_distance: 
	continue 
	
	# 扩展下一个城市 
	for next_city in range(n): 
	if next_city not in visited: 
	new_visited = frozenset(visited | {next_city}) 
	new_dist = current_dist + city_distances[current_city][next_city] 
	new_path = path + [next_city] 
	
	# 简化限界函数：当前距离 + 剩余城市的最小距离之和 
	remaining_cities = [c for c in range(n) if c not in new_visited] 
	if remaining_cities: 
	min_remaining = sum(min(city_distances[c][nc] for nc in remaining_cities if nc != c) for c in remaining_cities) 
	else: 
	min_remaining = 0 
	new_bound = new_dist + min_remaining 
	
	heapq.heappush(heap, (new_bound, new_dist, next_city, new_visited, new_path)) 
	
	return min_distance, best_path 
	
	# 测试：4个城市的距离矩阵 
	distances = [ 
	[0, 10, 15, 20], 
	[10, 0, 35, 25], 
	[15, 35, 0, 30], 
	[20, 25, 30, 0] 
	] 
	min_dist, path = tsp(distances) 
	print(f"最短路径：{path}，距离：{min_dist}") # 输出：最短路径：[0, 1, 3, 2, 0]，距离：80

性能分析
时间复杂度：取决于解空间大小和限界函数的有效性，最坏情况下仍为 O((n−1)!) O((n-1)!) O((n−1)!)，但剪枝可显著优化；
空间复杂度：O(n22n) O(n^2 2^n) O(n22n)（存储优先级队列中的状态）。
16.6.3 适用场景
分支限界法适用于求解最优解且解空间较大的问题，典型应用包括：
旅行商问题（TSP）；
0-1背包问题（求最大价值）；
整数规划问题；
电路设计（最小成本电路）。
16.7 本章总结
本章介绍的五种算法设计策略是解决复杂问题的通用框架，其核心思想与适用场景总结如下：

选择策略时，需根据问题的特性（子问题是否独立、是否有重叠、是否需最优解等）综合判断。实际应用中，多种策略可能结合使用（如动态规划+贪心、回溯+分支限界），关键是理解每种策略的底层逻辑，灵活应对不同场景。
16.8 思考题
1.用动态规划解决“编辑距离”问题（计算将一个字符串转换为另一个的最少操作次数，操作包括插入、删除、替换）。
2.证明贪心算法在“活动选择问题”中能得到最优解（提示：反证法，假设存在不包含贪心选择的最优解，推出矛盾）。
3.用回溯法解决“子集和”问题（给定数组和目标和，找出所有和为目标的子集），并添加剪枝条件（如当前和>目标和时停止搜索）。
4.对比动态规划和分支限界法在“0-1背包问题”中的应用，分析时间复杂度差异。
5.设计一个算法，用最少的硬币兑换一定金额，若硬币面额不满足贪心选择性质（如1、3、4元），请用动态规划实现。

本站原创，转载请注明出处：https://www.xin3721.com/python3/python49320.html