早点收手
约 10 分钟
枚举时,如果发现某个方向接下去肯定不可能有答案,就立刻停手、不再往下试,这叫剪枝。就像走迷宫,发现前面是死胡同马上退回换路,而不是撞到墙才回头,能省下大量无用功。
举例:从若干正整数里找两个数之和等于 。若已排好序,当第一个数只能取到 、而剩下最大的搭档也只有一位数(最多 ),那 ,再怎么配都不够,这一支可直接砍掉。
sort(a, a + n);
for (int i = 0; i < n; i++) {
if (a[i] + a[n-1] < target) continue; // 配最大都不够,跳过
if (a[i] * 2 > target) break; // 自己都超一半,后面更大,收工
// ... 正常查找搭档
}
continue 跳过没戏的当前项,break 直接结束整个循环。剪枝不改变答案的正确性,只是提前避开注定失败的分支,是给暴力搜索、DFS 提速的常用手段。剪得越准,省得越多。
小纸条
找两数之和为 20 的组合时,第一个数取到 3,还有必要试它配一位数吗?(最大才 3+9=12)
登录 后可看答案