1. 算法策略实战精要

下午题中的算法策略就像工具箱里的不同工具，每种都有最适合的使用场景。我当年备考时最大的误区就是死记硬背模板，直到实际刷题才发现理解本质特征才是关键。举个例子，分治法和动态规划都涉及子问题分解，但前者像拆积木（独立求解），后者更像拼马赛克（子问题重叠需要查表）。

1.1 四大算法特征识别

分治法的典型标志是：

• 问题可以等分为独立子问题（如归并排序的左右半边）
• 递归式通常呈现T(n)=aT(n/b)+f(n)形式
• 代码中常见数组分段操作（begin/mid/end三件套）

# 经典二分查找模板 def binary_search(arr, left, right, target): if right >= left: mid = left + (right - left) // 2 if arr[mid] == target: return mid elif arr[mid] > target: return binary_search(arr, left, mid-1, target) # 左半段 else: return binary_search(arr, mid+1, right, target) # 右半段 return -1

动态规划的三大识别特征：

1. 最优子结构（全局最优包含局部最优）
2. 重叠子问题（递归树有重复计算节点）
3. 状态转移方程（如斐波那契数列的dp[i]=dp[i-1]+dp[i-2]）

2. 代码填空破题技巧

2.1 递归边界条件定位

递归就像俄罗斯套娃，必须有个最小的娃娃作为终止条件。在代码填空中，递归出口通常出现在这三个位置：

• 数组/链表遍历结束时（指针==null或index>=length）
• 数值达到临界值时（如阶乘的n==1）
• 问题规模足够小时（如归并排序的区间长度<=1）

# 快速排序填空常见陷阱 def quick_sort(arr, low, high): if low < high: # 填空高频点1：递归继续条件 pivot = partition(arr, low, high) quick_sort(arr, low, pivot-1) # 填空高频点2：左子区间 quick_sort(arr, pivot+1, high) # 填空高频点3：右子区间

2.2 动态规划填表规律

DP类填空要特别注意：

1. 初始化条件（通常dp[0]、dp[1]需要特殊处理）
2. 状态转移方向（自底向上还是自顶向下）
3. 返回值位置（可能是dp数组末尾或最大值）

比如背包问题中：

def knapsack(W, wt, val, n): dp = [[0]*(W+1) for _ in range(n+1)] for i in range(1, n+1): # 填空点1：物品循环 for w in range(1, W+1): # 填空点2：容量循环 if wt[i-1] <= w: dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], # 填空点3：状态转移 dp[i-1][w]) else: dp[i][w] = dp[i-1][w] # 填空点4：继承状态 return dp[n][W]

3. 贪心与回溯实战对比

3.1 贪心选择性质验证

贪心算法就像吃自助餐——每次拿最贵的食物。验证贪心选择性质需要证明：

1. 局部最优能导致全局最优
2. 无后效性（当前选择不影响后续选择）

典型错题：硬币找零问题（当硬币面值为[1,3,4]时，贪心法找6元会得到4+1+1而非最优解3+3）

3.2 回溯法的剪枝优化

回溯法就像走迷宫，遇到死路要回撤。代码填空中常见：

• 路径选择列表（for循环遍历选项）
• 终止条件（找到解或超出限制）
• 状态回退（撤销当前选择）

def backtrack(路径, 选择列表): if 满足结束条件: # 填空点1：终止条件 结果.append(路径) return for 选择 in 选择列表: if 剪枝条件: # 填空点2：可行性剪枝 continue 做选择 # 填空点3：状态标记 backtrack(路径, 选择列表) 撤销选择 # 填空点4：状态回退

4. 经典案例深度剖析

4.1 装箱问题双解法

问题描述：将n个物品装入容量为C的箱子，求最少箱子数。

贪心解法（近似解）：

def first_fit(items, C): bins = [0] # 初始化第一个箱子 for item in items: placed = False for i in range(len(bins)): if bins[i] + item <= C: # 填空点1：检查容量 bins[i] += item # 填空点2：放入物品 placed = True break if not placed: bins.append(item) # 填空点3：开新箱 return len(bins)

动态规划解法（精确解）：

def min_bins(items, C): n = len(items) dp = [float('inf')] * (n + 1) dp[0] = 0 for i in range(1, n+1): current_weight = 0 min_bins = float('inf') for j in range(i, 0, -1): current_weight += items[j-1] if current_weight > C: break min_bins = min(min_bins, dp[j-1] + 1) # 关键状态转移 dp[i] = min_bins return dp[n]

4.2 合并排序关键填空

归并排序是分治法的经典案例，填空常出现在：

1. 递归终止条件（序列长度<=1）
2. 合并时的临时数组操作
3. 左右子序列的边界处理

def merge_sort(arr, left, right): if left < right: # 填空点1：递归继续条件 mid = (left + right) // 2 merge_sort(arr, left, mid) merge_sort(arr, mid+1, right) merge(arr, left, mid, right) def merge(arr, left, mid, right): temp = [0]*(right-left+1) i, j, k = left, mid+1, 0 while i <= mid and j <= right: # 填空点2：双指针移动 if arr[i] <= arr[j]: temp[k] = arr[i] i += 1 else: temp[k] = arr[j] # 填空点3：右半部元素放入 j += 1 k += 1 while i <= mid: # 填空点4：左剩余处理 temp[k] = arr[i] i += 1 k += 1 while j <= right: # 填空点5：右剩余处理 temp[k] = arr[j] j += 1 k += 1 for p in range(len(temp)): arr[left+p] = temp[p] # 填空点6：回写数组

5. 避坑指南与实战建议

5.1 常见错误类型

1. 边界错误：二分查找中的mid计算应写作left + (right-left)//2而非(left+right)//2，防止整数溢出
2. 状态混淆：动态规划中dp[i][j]的定义要始终保持一致，比如背包问题中i表示前i个物品而非第i个物品
3. 剪枝遗漏：回溯法中忘记处理重复元素会导致结果集冗余（如全排列问题需维护visited数组）

5.2 调试技巧

• 递归树法：画出前3层递归调用，验证参数传递是否正确
• 打印日志法：在递归入口/出口打印关键变量（适用于深度≤5的情况）
• 小黄鸭调试法：向他人（或玩偶）逐行解释代码逻辑，经常能自己发现逻辑漏洞

记得去年做过的矩阵链乘问题，状态转移方程调试了整整3小时，最后发现是区间长度循环的边界设错了。这种痛只有经历过的人才懂——所以现在我的代码注释里一定会标明每个循环变量的具体含义。