贪心算法与回溯算法详解

一、贪心算法深度解析

1.1 贪心算法核心思想

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优（最有利）的选择，从而希望导致结果是全局最优的算法策略。

贪心算法的基本特性：

1. 贪心选择性质：局部最优选择能导致全局最优解

2. 最优子结构：问题的最优解包含子问题的最优解

3. 无后效性：某个状态以前的过程不会影响以后的状态

1.2 贪心算法适用场景

贪心算法适用于具有贪心选择性质的问题，常见的应用场景包括：

1. 活动选择问题

2. 霍夫曼编码

3. 最小生成树（Prim和Kruskal算法）

4. 最短路径（Dijkstra算法）

5. 背包问题的部分变体

二、贪心算法经典题目详解

2.1 LeetCode 122：买卖股票的最佳时机 II

问题描述

text

给定一个数组 prices，其中 prices[i] 是某支股票第 i 天的价格。 设计一个算法计算最大利润，可以完成任意笔交易（买卖多次）。 限制：不能同时参与多笔交易（必须在再次购买前出售之前的股票）。

贪心策略分析

核心思路：将股票价格视为折线图，所有上升区间的收益和就是最大利润。

数学证明：
假设有连续n天的价格：p₁, p₂, ..., pₙ
总利润 = Σ(max(0, pᵢ - pᵢ₋₁))，其中 i = 2 to n

为什么贪心有效：

• 单次交易：在最低点买入，最高点卖出

• 多次交易：可以分解为多个单日交易的和

• 对于任意区间[a,b]，总收益 = p_b - p_a = Σ(pᵢ - pᵢ₋₁) (i从a+1到b)

代码实现

python

class Solution: def maxProfit(self, prices: List[int]) -> int: """ 贪心算法实现 时间复杂度：O(n) 空间复杂度：O(1) """ max_profit = 0 for i in range(1, len(prices)): # 只要今天比昨天价格高，就累加利润 if prices[i] > prices[i - 1]: max_profit += prices[i] - prices[i - 1] return max_profit

动态规划对比解法

python

class Solution: def maxProfit(self, prices: List[int]) -> int: """ 动态规划解法 dp[i][0]: 第i天不持有股票的最大利润 dp[i][1]: 第i天持有股票的最大利润 """ if not prices: return 0 n = len(prices) dp = [[0, 0] for _ in range(n)] # 初始化 dp[0][0] = 0 # 第0天不持有 dp[0][1] = -prices[0] # 第0天持有（需要买入） for i in range(1, n): # 第i天不持有：昨天就不持有，或昨天持有今天卖出 dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) # 第i天持有：昨天就持有，或昨天不持有今天买入 dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) return dp[n-1][0]

算法复杂度分析

• 贪心算法：O(n)时间，O(1)空间

• 动态规划：O(n)时间，O(n)空间（可优化为O(1)）

2.2 LeetCode 455：分发饼干

问题描述

text

假设你是一位家长，要给孩子们分发饼干。 每个孩子 i 有胃口值 g[i]，每块饼干 j 有尺寸 s[j]。 如果 s[j] >= g[i]，则可以将饼干 j 分给孩子 i。 目标：尽可能满足更多的孩子，返回最大数量。

贪心策略分析

两种贪心策略：

1. 小胃口优先：优先满足胃口小的孩子

2. 大饼干优先：优先用大饼干满足大胃口

正确性证明（小胃口优先）：

• 设最优解满足的孩子集合为S

• 贪心算法满足的孩子集合为G

• 用数学归纳法证明|G| = |S|

代码实现

python

class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: """ 贪心算法：小胃口优先 时间复杂度：O(nlogn + mlogm) 空间复杂度：O(1) """ # 排序：胃口和饼干都从小到大 g.sort() s.sort() child = 0 cookie = 0 while child < len(g) and cookie < len(s): # 如果当前饼干能满足当前孩子 if s[cookie] >= g[child]: child += 1 # 满足一个孩子 cookie += 1 # 无论是否满足，饼干都要尝试下一个 return child

大饼干优先策略

python

class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: """ 贪心算法：大饼干优先 时间复杂度：O(nlogn + mlogm) 空间复杂度：O(1) """ # 排序：胃口和饼干都从大到小 g.sort(reverse=True) s.sort(reverse=True) child = 0 cookie = 0 while child < len(g) and cookie < len(s): # 如果当前饼干能满足当前孩子（大胃口） if s[cookie] >= g[child]: cookie += 1 # 使用这块饼干 child += 1 # 满足一个孩子 else: child += 1 # 这个孩子无法满足，尝试下一个孩子 return cookie

算法复杂度分析

• 时间复杂度：O(nlogn + mlogm)，主要是排序的开销

• 空间复杂度：O(1) 或 O(logn + logm)（取决于排序算法）

2.3 LeetCode 659：分割数组为连续子序列

问题描述

text

给定一个按升序排序的整数数组（可能包含重复数字）。 判断是否能将数组分割成一个或多个长度至少为3的子序列， 其中每个子序列都由连续整数组成。

问题分析

输入示例分析：

• [1,2,3,3,4,5] → True，可分割为[1,2,3]和[3,4,5]

• [1,2,3,3,4,4,5,5] → True，可分割为[1,2,3,4,5]和[3,4,5]

• [1,2,3,4,4,5] → False，无法分割

贪心策略

核心思路：优先延长现有序列，无法延长时创建新序列

具体策略：

1. 统计每个数字的出现次数

2. 维护以每个数字结尾的序列数量

3. 遍历数组，对于每个数字num：

   • 如果存在以num-1结尾的序列，将num接在后面

   • 否则，检查能否以num开头创建新序列（需要num+1, num+2存在）

   • 如果都不行，返回False

代码实现

python

import collections class Solution: def isPossible(self, nums: List[int]) -> bool: """ 贪心算法：优先延长现有序列 时间复杂度：O(n) 空间复杂度：O(n) """ # 统计每个数字的剩余次数 count = collections.Counter(nums) # 记录以某个数字结尾的序列数量 end = collections.Counter() for num in nums: if count[num] == 0: continue # 该数字已用完 count[num] -= 1 # 使用这个数字 # 情况1：能接到某个序列后面 if end.get(num - 1, 0) > 0: end[num - 1] -= 1 end[num] += 1 # 情况2：能作为新序列的开头 elif count.get(num + 1, 0) > 0 and count.get(num + 2, 0) > 0: count[num + 1] -= 1 count[num + 2] -= 1 end[num + 2] += 1 # 情况3：无法处理 else: return False return True

堆解法（另一种思路）

python

import heapq from collections import defaultdict class Solution: def isPossible(self, nums: List[int]) -> bool: """ 使用堆的解法 时间复杂度：O(nlogn) 空间复杂度：O(n) """ # 记录以某个数字结尾的序列长度（使用最小堆） chains = defaultdict(list) for num in nums: # 如果存在以num-1结尾的序列 if chains[num - 1]: # 取出最短的序列 length = heapq.heappop(chains[num - 1]) # 将当前数字接在后面 heapq.heappush(chains[num], length + 1) else: # 创建新序列 heapq.heappush(chains[num], 1) # 检查所有序列长度是否都>=3 for lengths in chains.values(): if lengths and min(lengths) < 3: return False return True

算法复杂度分析

• 哈希表解法：O(n)时间，O(n)空间

• 堆解法：O(nlogn)时间，O(n)空间

三、回溯算法深度解析

3.1 回溯算法核心思想

回溯算法（Backtracking）是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会丢弃该解，回退到上一步尝试其他选择。

回溯算法的基本框架：

python

def backtrack(路径, 选择列表): if 满足结束条件: 结果.append(路径.copy()) return for 选择 in 选择列表: if 选择不合法: continue 做选择 backtrack(新路径, 新选择列表) 撤销选择

回溯算法的三个关键要素：

1. 路径：已经做出的选择

2. 选择列表：当前可以做的选择

3. 结束条件：到达决策树底层，无法再做选择

3.2 回溯算法适用场景

回溯算法适用于需要搜索所有可能解的问题：

1. 组合问题：N个数中按规则找出k个数的组合

2. 排列问题：N个数按一定规则全排列

3. 子集问题：一个N个数的集合有多少符合条件的子集

4. 棋盘问题：N皇后、解数独等

5. 切割问题：字符串按一定规则切割

6. 子集树问题：从集合中找出满足条件的子集

四、回溯算法经典题目详解

4.1 LeetCode 46：全排列问题

问题描述

text

给定一个不含重复数字的数组 nums，返回其所有可能的全排列。 可以按任意顺序返回答案。

回溯策略分析

排列问题的特点：

• 每个元素只能使用一次

• 顺序不同算作不同的排列

• 需要记录哪些元素已经使用过

决策树深度：n（数组长度）
决策树宽度：每层可选元素逐渐减少

代码实现

python

class Solution: def permute(self, nums: List[int]) -> List[List[int]]: """ 回溯算法：全排列 时间复杂度：O(n * n!) 空间复杂度：O(n) """ def backtrack(path, used): # 结束条件：路径长度等于数组长度 if len(path) == len(nums): result.append(path[:]) # 深拷贝 return for i in range(len(nums)): # 剪枝：跳过已使用的元素 if used[i]: continue # 做选择 used[i] = True path.append(nums[i]) # 进入下一层决策树 backtrack(path, used) # 撤销选择 path.pop() used[i] = False result = [] backtrack([], [False] * len(nums)) return result

交换法实现（不使用额外空间）

python

class Solution: def permute(self, nums: List[int]) -> List[List[int]]: """ 交换法实现全排列 时间复杂度：O(n * n!) 空间复杂度：O(n) 递归栈空间 """ def backtrack(first=0): # 所有数都填完了 if first == len(nums): result.append(nums[:]) return for i in range(first, len(nums)): # 动态维护数组 nums[first], nums[i] = nums[i], nums[first] # 继续递归填下一个数 backtrack(first + 1) # 撤销交换 nums[first], nums[i] = nums[i], nums[first] result = [] backtrack() return result

算法复杂度分析

• 时间复杂度：O(n × n!)

  • 总共有n!个排列

  • 每个排列需要O(n)时间复制到结果中

• 空间复杂度：O(n)

  • 递归深度为n

  • used数组或交换操作需要O(n)空间

变体：LeetCode 47（含重复数字的全排列）

python

class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: """ 含重复数字的全排列 关键：排序 + 剪枝 """ def backtrack(path, used): if len(path) == len(nums): result.append(path[:]) return for i in range(len(nums)): # 剪枝条件1：该数字已使用 if used[i]: continue # 剪枝条件2：重复数字的处理 if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue used[i] = True path.append(nums[i]) backtrack(path, used) path.pop() used[i] = False nums.sort() # 排序以便剪枝 result = [] backtrack([], [False] * len(nums)) return result

4.2 LeetCode 22：括号生成

问题描述

text

数字 n 代表生成括号的对数，设计一个函数， 生成所有可能的并且有效的括号组合。

问题分析

有效括号的条件：

1. 左括号数量 ≤ n

2. 右括号数量 ≤ 左括号数量（始终成立）

3. 最终左括号数量 = 右括号数量 = n

回溯树的特征：

• 每个节点有最多两个分支：添加'('或')'

• 深度：最多2n

• 叶子节点数：第n个卡特兰数 Cₙ = (1/(n+1)) × C(2n, n)

代码实现

python

class Solution: def generateParenthesis(self, n: int) -> List[str]: """ 回溯算法：括号生成 时间复杂度：O(4^n/√n)，卡特兰数 空间复杂度：O(n) """ def backtrack(s, left, right): # 结束条件：字符串长度达到2n if len(s) == 2 * n: result.append(s) return # 选择1：添加左括号（如果左括号数量小于n） if left < n: backtrack(s + '(', left + 1, right) # 选择2：添加右括号（如果右括号数量小于左括号数量） if right < left: backtrack(s + ')', left, right + 1) result = [] backtrack('', 0, 0) return result

动态规划解法

python

class Solution: def generateParenthesis(self, n: int) -> List[str]: """ 动态规划解法 dp[i]: 生成i对括号的所有组合 状态转移：dp[i] = "(" + dp[p] + ")" + dp[q]，其中 p + q = i-1 """ if n == 0: return [] dp = [[] for _ in range(n + 1)] dp[0] = [""] # 0对括号的情况 for i in range(1, n + 1): for p in range(i): q = i - 1 - p for left in dp[p]: for right in dp[q]: dp[i].append(f"({left}){right}") return dp[n]

闭合数解法（数学方法）

python

class Solution: def generateParenthesis(self, n: int) -> List[str]: """ 闭合数解法（基于数学原理） 任何一个括号序列可以表示为：(A)B 其中A和B都是有效的括号序列 """ if n == 0: return [""] result = [] for i in range(n): for left in self.generateParenthesis(i): for right in self.generateParenthesis(n - 1 - i): result.append(f"({left}){right}") return result

算法复杂度分析

回溯算法：

• 时间复杂度：O(4ⁿ/√n)

  • 这是第n个卡特兰数的渐近复杂度

  • 精确值是 Cₙ = (1/(n+1)) × C(2n, n)

• 空间复杂度：O(n)

  • 递归深度为2n

  • 存储结果需要 O(4ⁿ/√n × 2n) 空间

动态规划：

• 时间复杂度：O(4ⁿ/√n)，与回溯相同

• 空间复杂度：O(4ⁿ/√n)，需要存储所有中间结果

括号生成问题的数学背景

括号生成的数量是卡特兰数，其递推公式为：

text

C₀ = 1 Cₙ₊₁ = Σ(Cᵢ × Cₙ₋ᵢ)，i从0到n

前几个卡特兰数：

text

n=0: 1 n=1: 1 n=2: 2 n=3: 5 n=4: 14 n=5: 42 n=6: 132

五、贪心与回溯算法对比

5.1 算法思想对比

5.2 选择算法的指导原则

1. 问题类型判断：

   • 如果问题要求所有可能解→ 回溯

   • 如果问题要求单个最优解→ 考虑贪心或动态规划

2. 问题规模考虑：

   • 小规模问题（n ≤ 20）→ 回溯可能可行

   • 大规模问题 → 需要更高效的算法（贪心、动态规划）

3. 问题特征分析：

   • 具有最优子结构和贪心选择性质→ 贪心算法

   • 需要穷举所有可能→ 回溯算法

六、面试技巧与常见问题

6.1 贪心算法面试技巧

1. 如何证明贪心选择的正确性：

   • 替换法：证明贪心选择可以替换最优解中的选择而不降低质量

   • 归纳法：证明贪心选择的前缀可以扩展为全局最优解

   • 反证法：假设贪心选择不是最优，导出矛盾

2. 常见问题：

   • "为什么贪心算法在这里有效？"

   • "如何证明你的贪心策略是最优的？"

   • "如果问题条件改变，你的算法还适用吗？"

6.2 回溯算法面试技巧

1. 剪枝优化技巧：

   • 可行性剪枝：提前排除不可能的解

   • 最优性剪枝：在求最优解时，提前排除劣于当前最优的解

   • 对称性剪枝：避免重复计算对称解

2. 常见问题：

   • "如何避免重复计算？"

   • "如何设计剪枝条件？"

   • "递归深度可能有多大？是否会导致栈溢出？"

七、扩展学习与练习题目

7.1 贪心算法扩展题目

1. LeetCode 55：跳跃游戏

2. LeetCode 134：加油站

3. LeetCode 253：会议室 II

4. LeetCode 406：根据身高重建队列

5. LeetCode 621：任务调度器

7.2 回溯算法扩展题目

1. LeetCode 39：组合总和

2. LeetCode 78：子集

3. LeetCode 79：单词搜索

4. LeetCode 51：N皇后

5. LeetCode 93：复原IP地址

八、总结与思考

8.1 贪心算法的本质

贪心算法的核心在于局部最优选择能导致全局最优。这种性质并不总是成立，因此在使用贪心算法时，必须仔细分析问题特性，并给出正确性证明。

8.2 回溯算法的本质

回溯算法本质上是深度优先搜索在解空间上的应用，通过剪枝减少不必要的搜索，通过撤销选择实现状态回溯。

8.3 算法选择的心智模型

当面对一个新问题时，可以按照以下流程思考：

text

1. 判断问题类型（组合、排列、最优化等） 2. 分析问题规模（数据范围） 3. 考虑问题特性（重叠子问题、最优子结构等） 4. 尝试简化问题（特殊化、一般化） 5. 选择合适算法框架 6. 实现并验证

8.4 算法学习的建议

1. 理解本质：不要死记硬背模板，要理解算法背后的思想

2. 多画图：对于回溯问题，画决策树有助于理解

3. 多做比较：对比不同解法的优缺点

4. 注重证明：理解算法正确性的证明过程

5. 实际应用：将算法思想应用到实际问题中

贪心算法和回溯算法是算法学习中的重要组成部分，它们分别代表了"局部最优"和"全局搜索"两种不同的算法设计思想。掌握这两种算法，不仅有助于解决具体问题，更能培养良好的算法思维和分析能力。

通过本文的详细解析，希望读者能够：

1. 深入理解贪心和回溯算法的核心思想

2. 掌握常见问题的解题模板和优化技巧

3. 培养算法分析能力和证明能力

4. 在实际面试和工作中灵活应用这些算法