迭代加深搜索（IDDFS）NOIP

💡 核心思想

迭代加深搜索（IDDFS）是一种限制搜索深度的 DFS：从深度 1 开始，逐步增加深度限制，每次在限制深度内做 DFS。它结合了 DFS 的空间优势和 BFS 的最优性保证，特别适合状态空间巨大但最优解深度不大的问题。

🎯 直觉理解

迭代加深搜索是"从小到大限制深度反复搜"：先只允许走 1 步搜一遍，再允许 2 步、3 步……直到找到答案。听起来重复很多遍，但每层规模是指数增长，重复搜的花费远小于最后一层的规模。

它解决的痛点是：DFS 不知道答案深度会卡在深分支里，BFS 又可能内存爆炸。迭代加深两者兼顾——空间同 DFS（$O(深度)$），还能保证找到最浅解。

典型场景：状态空间很大、答案深度未知的搜索题（如骑士精神、八数码类）。深度上限就是答案层数，找到解的那个深度一定是最优深度。

📝 算法流程

1. 设定初始深度限制 maxDepth = 1
2. 在 maxDepth 限制下做 DFS
3. 如果找到解，返回
4. 否则 maxDepth++，重复步骤 2
5. DFS 中：如果当前深度 > maxDepth，剪枝返回

$$\text{总节点数} \approx O(b^d) \text{，其中 }b\text{ 为分支因子，}d\text{ 为解深度}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;

bool found;
int maxDepth;

// 示例：在数字 1~n 中找和为 target 的最少个数（IDDFS 模板）
void dfs(int cur, int depth, int target) {
    if (found) return;
    if (cur == target) { found = true; return; }
    if (depth >= maxDepth) return; // 超过深度限制，剪枝
    if (cur > target) return;      // 剪枝：已经超过目标
    
    // 尝试加下一个数（分支）
    for (int i = 1; i <= 3 && !found; i++) // 每次可以 +1, +2, +3
        dfs(cur + i, depth + 1, target);
}

int iddfs(int target) {
    for (maxDepth = 1; ; maxDepth++) {
        found = false;
        dfs(0, 0, target);
        if (found) return maxDepth;
    }
}

int main() {
    cout << iddfs(10) << endl; // 最少 4 步：3+3+3+1
    return 0;
}

⚠️ 常见坑点

📚 相关题目