Neo's Blog

关于回溯，你一定要知道的

• Q: 回溯的定义与核心思想

A: 根据百度百科的定义，回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯算法（Backtrack）是一种试错思想，本质上是深度优先搜索。即：从问题的某一种状态出发，依次尝试现有状态可以做出的选择从而进入下一个状态。递归这个过程，如果在某个状态无法做更多选择，或者已经找到目标答案时，则回退一步甚至多步重新尝试，直到最终所有选择都尝试过。

• Q：回溯算法涉及到的一些概念

A: 问题的解空间（Solution Space)：针对一个问题的某一种枚举元素，我们做出多次枚举，这样子下来所有的解会构成一个树形结构，树的每一个节点是该问题的一个可能解，我们把这些可能解的集合称之为解空间。

状态（State of this problem)：当前的搜索深度，以及该深度的一些局面信息

选择（avaiable Choosen based on current state) ：基于当前状态能够进一步做出的选择

路径（Path of choosen for solving this problem）：为了解决这个问题，走到当前状态，每一步做出的选择构成了一个列表，这个列表称之为路径

结果集（Result: all paths which can slove this problem)：对于求解可行解或者所有解类型的回溯问题，我们需要把所有的可行路径记录下来，这个用来存储可行路径的容器我们称之为结果集

Q：回溯算法的三要素

A：路径：已经做出的选择

选择列表：当前状态可以做出的选择

结束条件：选择列表为空，或者找到目标

地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。

一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 k 的格子。

请问该机器人能够达到多少个格子？

样例1
输入：k=7, m=4, n=5

输出：20
样例2
输入：k=18, m=40, n=40

输出：1484

解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
但是，它不能进入方格（35,38），因为3+5+3+8 = 19。

解题思路

状态： + 访问位图

选择: 四个方向

路径：该问题不需要

结果集：计算总数

结束条件： 没有更多选择

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
public:
    int t;
    vector<bool> visit;
    int cnt;
    
    bool check(int i, int j) {
        return (i / 10 + i % 10 + j / 10 + j % 10) <= t;
    }
    
    void dfs(int i, int j, int rows, int cols){
        if (!check(i, j)) return;
        visit[i * cols + j] = true;
        cnt++;
        
        int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
        
        for (int k = 0; k < 4; ++k) {
            int ni = i + dx[k], nj = j + dy[k];
            if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && !visit[ni * cols + nj]) {
                dfs(ni, nj, rows, cols);
            }
        }
    }
    
    int movingCount(int threshold, int rows, int cols)
    {
        if (!rows && !cols) return 0;
        t = threshold;
        visit = vector<bool>((rows + 1) * (cols + 1), false);
        dfs(0, 0, rows, cols);
        return cnt;
    }
};

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。

如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

注意：

输入的路径不为空；
所有出现的字符均为大写英文字母；
样例
matrix=
[
[“A”,”B”,”C”,”E”],
[“S”,”F”,”C”,”S”],
[“A”,”D”,”E”,”E”]
]

str=”BCCE” , return “true”

str=”ASAE” , return “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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
public:
    bool dfs(vector<vector<char>>& matrix, string &str, int u, int x, int y) {
        //视频中的错误写法（测试用例不全导致）
        //if (u == str.length()) return true;
        //if (matrix[sx][y] != str[u]) return false;

        //肯定不合适
        if (matrix[x][y] != str[u]) return false;
        //已经到底了，返回ok
        if (u == str.length() - 1) return true; 

        int t = matrix[x][y];
        matrix[x][y] = '#';

        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

        for (int i = 0; i < 4; ++i) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size()) {
                if (dfs(matrix, str, u + 1, a, b)) return true;
            }
        }

        matrix[x][y] = t;
        return false;
    }

    bool hasPath(vector<vector<char>>& matrix, string &str) {
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[i].size(); ++j) {
                if (dfs(matrix, str, 0, i, j))
                {
                    return true;
                }
            }
        }

        return false;
    }
};

关于二叉树，你一定要知道的

• Q：二叉树遍历

A: 作为图的一种简单形式，树也有两种遍历方式：广度优先、深度优先；广度优先的话，即对应二叉树的按层次遍历；深度优先的话，我们可以按照中间节点的访问顺序， 进一步分为先序遍历（中、左、右）、中序遍历（左、中、右）、后序遍历（左、右、中）。

• Q：二叉树的层次遍历（BFS遍历）

A: 通常我们借助队列（queue)来辅助完成分层遍历。 还有某些情况，我们需要了解到每一个节点的深度（也就是位于第几层）。对于这种要求，我在下面的代码模版中给出了一种解决方案，供参考。

位操作

关于位操作，你一定要知道的

位操作的常见技巧

第一个需要掌握的技巧是n & (n - 1)，通过该操作我们可以让n的最后一个1变为0。

第二个需要掌握的技巧是lowbit(n) = n & (-n) ,lowbit操作可以让我们获取到n的低位。

第三个需要知道的是二进制表示下不进位，例如：XOR又称作不进位加法。

第四个技巧在于 n XOR 1成对变换。

最后，掌握二进制位状态压缩的常见操作

位操作相关的经典题目

另外，还有一种状态表示：
即F[i; v] 表示前i 件物品恰放入一个容量为v 的背包可以获得的最大价值。则其状态转移方程便是：

F[i,v] = max(F[i -1, v], F[i-1 , v-C[i]] + W[i])

这样子表示状态后，目标变为F[N, M]

eg. 划分数组为两个相等的子集

找sum一半

DP概念

动态规划是运筹学的一个分支，是一种求解多阶段决策过程最优化问题的数学方法。要搞清楚它，首先需要搞清楚几个基本概念。

阶段：整个决策过程可以按某个（空间、时间或其它）标准分为多个步骤，每一步称为一个阶段。比如下棋，走一步就可以认为是一个阶段。

状态：状态表示在每个阶段我们关注的决策相关的影响因素的情况。比如下棋到某一步时，此刻棋盘上所有棋子的位置就是此阶段的状态。状态通常可以用一个或多个变量来描述。

决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择行动方法称为决策。比如下棋到某一步时，决定下一步怎么走，就是一步决策，也叫单阶段决策。决策通常也可以用变量来描述。

策略：由每个阶段的决策组成的序列称为策略，也就是多阶段决策。比如下棋，从开始下到结束的每一步走法构成了一个策略。策略可能有很多种，其中达到最优效果的策略称为最优策略。

状态转移方程：从一个阶段到下一个阶段的状态变化，称为状态转移，如果这个变化可以用方程来描述，则称之为状态转移方程。

无后效性：说的是一旦某个阶段的状态确定，则此后过程的演变不再受此前各种状态及决策的影响。也就是说历史信息不会影响我们以后的决策。比如下棋，现在已经有一个棋面，有可能是随机摆成的，也可能是认真下成这样的，但是不管怎样这不影响我们去决定下一步应该怎么下。当前的棋面是唯一影响未来的东西。

最优⼦结构：如果每个阶段的最优状态可以从之前某个或某些阶段的某个或某些状态直接得到，也就是说一个问题的最优解可以由其子问题的最优解来得到，我们称其具有最优子结构。

重叠⼦问题：在求解一个问题时需要先求解其子问题，子问题又有子问题，若在求解过程中需要重复求解某些子问题，这些子问题称为重叠子问题。对于重叠子问题不需要重复求解，只需要求解一次，然后记录下来，以后每次查询就可以了，可以大大降低运行时间，即用空间换时间。

参考：https://blog.csdn.net/tyst08/article/details/106412008

简单起见，下面用大家非常熟悉的求斐波拉契数列的过程来说明这几个概念。斐波拉契数列的公式为：

f(1)=f(2)=1

f(n)=f(n−1)+f(n−2)(n≥3)

假设我现在想计算第10个非波那契数，那么计算每一个斐波拉契数的过程就是一个阶段，每一个斐波拉契数就是这个问题的一个状态。按照公式计算就是决策。每一步都按公式算就是策略。状态转移方程为 f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n) = f(n-1) + f(n-2)f(n)=f(n−1)+f(n−2)。求一个新数字只需要之前的两个状态，与怎么得到这个状态值无关，所以具有无后效性。每个阶段的状态即斐波拉契数可以由之前的两个状态得到，所以具有最优子结构。根据公式，求 f ( n ) f(n)f(n) 时需要求 f ( n − 2 ) f(n-2)f(n−2)，求 f ( n − 1 ) f(n-1)f(n−1) 时也需要求 f ( n − 2 ) f(n-2)f(n−2)，所以有重叠⼦问题。

动态规划就是利用最优子结构，把多阶段决策过程的最优化问题转化为一系列单阶段最优化问题，然后逐个求解子问题。在每一个子问题的求解中，均可以利用了它前面的子问题的最优化结果，依次进行，直到得到最后一个子问题的最优解，也就是整个问题的最优解。

动态规划的流程一般可以分为以下几步：

1. 对决策过程划分阶段。
2. 对各阶段确定状态变量。
3. 根据状态变量确定每个决策的开销以及最终的目标函数。
4. 建立各阶段状态变量的转移过程，确定状态转移方程。
5. 根据状态转移方程用代码来实现，一般可以用递归，注意对重叠子问题要记录其解。

动态规划优化策略

1. 费用提前/延后计算：没有关于某个维度的限制条件，这个维度纯粹用来计算费用，考虑是否可以提前计算
2. 空间压缩

经典问题

常见的动态规划问题有哪些：

动态规划相关的经典题目

https://zhuanlan.zhihu.com/p/410411231

等差递减区间的个数【转斐波那契】