木易

# Road Map

升级路线：

  • 棋盘问题：51 -> 37 -> 490
  • 排列组合子集问题：77 -> 39 -> 46 -> 78
  • 其他搜索问题：17 -> 79 -> 93

# 回溯算法

“回溯”实际上是一种类似于枚举的搜索方式，在搜索过程中尝试枚举所有路径，当发现不满足搜索条件时，退回到上面的步骤选择其他路线继续尝试搜索，这种走不通就退回再走的技术为回溯法。

回溯法一般适用于 小规模数据量 但是情况较为复杂的问题，比如 八皇后、象棋等棋盘类问题。时间复杂度往往难以分析，不同的剪枝条件情况下，时间复杂度会有极大的不同；

对于性能要求较高的回溯算法，我们可以使用剪枝、迭代加深等方式进行优化。

# DFS & 递归 & 回溯 & 剪枝

这四种算法经常结合起来使用，用来解决几类问题

  • 排列组合子集问题
  • 棋盘搜索的问题

    往往是在一个棋盘上查找最短路径、路径方案数

  • 树形问题

    树形结构中的深度优先搜索

# 代码模板

# 递归

递归即为闭包

func dfs(){
    doSomeThing()
    dfs()
    doAnotherThing()
}
1
2
3
4
5

# 回溯

回溯法，又称 试探法，当探索到 某一步 时，发现原先 选择的路径 到不了目标，就退回一步重新选择，这种走不通就退回再走的方法叫做回溯法

func dfs(){
    change()
    dfs()
    unchange()
}
1
2
3
4
5

# dfs&递归&回溯&剪枝

dfs & 递归 & 回溯 & 剪枝 结合使用，代码模板

function dfs(){ // 深搜
    doCounter() // 统计结果
    doCut() // 剪枝
    for all router { // 遍历所有路径
        doSomeThing()   // 搜索处理，保存当前状态等
        change()    // 当前棋盘变化
        dfs()       // 递归
        unchange()  // 回溯棋盘变化（恢复现场）
        doAnotherThing()
    }
}
1
2
3
4
5
6
7
8
9
10
11

# 适用于解决的问题特征

  • 深度优先搜索经常用来处理数据量非常庞大的问题

    比如数独问题，用宽搜搜不完的

  • 常用于解决树形问题
  • 宽度优先搜索经常用来处理最短路径，或最短距离
  • 深度搜索不一定等于递归，也可以用循环来实现
  • 所谓回溯就是恢复初始状态（恢复现场）

    如果我们的状态是整个棋盘，就需要恢复现场，如果是某一个格子，就不需要恢复现场

# 经典问题

引入几个简单问题，帮助大家理解概念

  • 递归经典问题：汉诺塔
  • 回溯经典问题：八皇后

# 递归经典：汉诺塔

三座塔 A, B, C，求移动的最小次数

分三步：

  1. 把上面的 n-1，从A->B;
  2. 把最下面的盘子，从A->C;
  3. 把 B 上的 n-1，从B->A;

递归求解

function Hanoi(n) {
  if (n == 1) return 1;
  if (n == 2) return 3;
  return 2 * Hanoi(n - 1) + 1; // 可以通过递推公式得到
}
1
2
3
4
5

所有递归问题都可以转化为递推求解

比如题目LeetCode 62. Unique Paths (medium) (opens new window)可以使用递归求路径总数，也可以用动态规划，根据状态转换方程，递推求解

我的习惯是如果方便使用递推求解，可以直接递推，如果递归更容易理解，也可以递归

递归的问题是：容易出现爆栈，而且一旦逻辑出错，定位问题的难度也要高于递推

# 回溯经典：八皇后

八皇后问题是讲解回溯的经典案例

# 排列、组合、子集问题

排列、组合、子集问题是 dfs 中一类常见的问题，我们用接下来的三天时间练习这三种问题

题目特征：

  • 组合、排列、子集 问题 属于一类基础问题，有一些问题也可以抽象成求解组合、排列、子集
  • 这类问题数据量不会太大
  • 往往可以用DFS进行暴搜求解

# 排列问题

题目特征: 请枚举所有排列

# 46. 全排列 (opens new window)

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    boolean[] st;
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        st = new boolean[n];
        dfs(nums, 0, new ArrayList<>());
        return res;
    }
    void dfs(int[] nums, int d, List<Integer> path) {
        if (d == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (st[i]) continue;
            st[i] = true;
            path.add(nums[i]);
            dfs(nums, d + 1, path);
            path.remove(path.size() - 1);
            st[i] = false;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 组合问题

求所有组合方案

拓展：

# 子集问题

题目特征: 请枚举所有子集

# 78. 子集 (opens new window)

class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0, new ArrayList<>());
        return res;
    }
    void dfs(int[] nums, int d, List<Integer> path) {

        if (d == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        dfs(nums, d + 1, path);
        path.add(nums[d]);
        dfs(nums, d + 1, path);
        path.remove(path.size() - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 90. 子集 II (opens new window)

增加 boolean st[] 辅助剪枝

# 棋盘搜索

棋盘搜索一般配合 DFS + memorization

记忆化：记录中间状态，回溯的时候能够按照某种规则依次迭代所有状态

# 迷宫问题

# 其他小游戏

# 密码锁类棋盘搜索

← 0x24_广度优先搜索 →