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, mid1, right, target) # 右半段 return -1动态规划的三大识别特征最优子结构全局最优包含局部最优重叠子问题递归树有重复计算节点状态转移方程如斐波那契数列的dp[i]dp[i-1]dp[i-2]2. 代码填空破题技巧2.1 递归边界条件定位递归就像俄罗斯套娃必须有个最小的娃娃作为终止条件。在代码填空中递归出口通常出现在这三个位置数组/链表遍历结束时指针null或indexlength数值达到临界值时如阶乘的n1问题规模足够小时如归并排序的区间长度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, pivot1, high) # 填空高频点3右子区间2.2 动态规划填表规律DP类填空要特别注意初始化条件通常dp[0]、dp[1]需要特殊处理状态转移方向自底向上还是自顶向下返回值位置可能是dp数组末尾或最大值比如背包问题中def knapsack(W, wt, val, n): dp [[0]*(W1) for _ in range(n1)] for i in range(1, n1): # 填空点1物品循环 for w in range(1, W1): # 填空点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,3,4]时贪心法找6元会得到411而非最优解333.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, n1): 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合并时的临时数组操作左右子序列的边界处理def merge_sort(arr, left, right): if left right: # 填空点1递归继续条件 mid (left right) // 2 merge_sort(arr, left, mid) merge_sort(arr, mid1, right) merge(arr, left, mid, right) def merge(arr, left, mid, right): temp [0]*(right-left1) i, j, k left, mid1, 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[leftp] temp[p] # 填空点6回写数组5. 避坑指南与实战建议5.1 常见错误类型边界错误二分查找中的mid计算应写作left (right-left)//2而非(leftright)//2防止整数溢出状态混淆动态规划中dp[i][j]的定义要始终保持一致比如背包问题中i表示前i个物品而非第i个物品剪枝遗漏回溯法中忘记处理重复元素会导致结果集冗余如全排列问题需维护visited数组5.2 调试技巧递归树法画出前3层递归调用验证参数传递是否正确打印日志法在递归入口/出口打印关键变量适用于深度≤5的情况小黄鸭调试法向他人或玩偶逐行解释代码逻辑经常能自己发现逻辑漏洞记得去年做过的矩阵链乘问题状态转移方程调试了整整3小时最后发现是区间长度循环的边界设错了。这种痛只有经历过的人才懂——所以现在我的代码注释里一定会标明每个循环变量的具体含义。