剪枝

剪枝是在搜索时提前判断“这条路不可能出结果 / 不可能更优”，直接放弃，省掉后面一大片无用计算。它不改变答案，只砍掉注定无效的分支，是让暴搜从超时变通过的关键。

常见两类：可行性剪枝（当前状态已违反约束，往下走也无解）和最优性剪枝（当前已经不比已知最优解好，没必要继续）。举个最优性剪枝：

void dfs(int step, int cost) {
    if (cost >= ans) return;   // 已经不比最优解更好, 剪掉
    if (step == n) { ans = min(ans, cost); return; }
    for (int i = 0; i < k; i++) {
        dfs(step + 1, cost + w[i]);   // 选第 i 个, 累加代价后继续
    }
}

剪枝不改变最坏复杂度，但实战中往往能把运行时间砍掉几个数量级。

坑：一是剪枝条件必须严格正确，剪错了会漏掉真正的答案；二是像最优性剪枝要配合“先搜更可能优的分支”效果才好；三是别为了剪枝把判断写得太重，否则省下的时间还不够判断本身花的。