动态规划（Dynamic Programming）
动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。
动态规划的核心思想就是穷举求最值，列出正确的「状态转移方程」，才能正确地穷举。而且，你需要判断算法问题是否具备「最优子结构」，是否能够通过子问题的最值得到原问题的最值。另外，动态规划问题存在「重叠子问题」。
首先，明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| # 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
for 选择 in 所有可能的选择:
# 此时的状态已经因为做了选择而改变
result = 求最值(result, dp(状态1, 状态2, ...))
return result
# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)
|
子矩阵的最大和问题
以
LeetCode面试题 17.24. 最大子矩阵
举例
给定一个正整数和负整数组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。返回一个子矩阵左上角的行号和列号，右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
我们将二维转化为一维，对于矩阵的每一列，我们将其加在一起，成为了一维上的一个数，二维矩阵的和转化为了一维数组的和，如下图。
转化为求最大子序列和之后，假设给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。我们该如何解决呢？
1、状态定义：dp[i]为以nums[i]结尾的最大子序和。
2、状态转移方程：对于nums[i]有两种情况:一种是和前一个位置的子序列连着。$dp[i]=dp[i-1]+nums[i]$。第二种是以自己独立门户，从自己开始$dp[i]=nums[i]$。取其中最大值,可得状态转移方程为$dp[i]=max( dp[i-1] + nums[i] , nums[i] )$。
3、basecase:$dp[0]=nums[0]$。
观察发现，dp[i]只与dp[i-1]和nums[i]有关，所有我们可以将空间复杂度降到O(1)
同时对于$dp[i]=max(dp[i-1]+nums[i],nums[i])$,两种情况都加了nums[i]，只是前面多加了dp[i-1]，所有很容易推出，当dp[i-1]<0时，后者大，反之前者大
问题迎刃而解，题解如下：
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| /**
* @author: Juncker chan
* @date: 2024.10.25
* @details: 子矩阵的最大和问题
**/
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int getMaxMatrixSum(vector<vector<int>>& matrix) {
int maxsum = INT_MIN;
int dp_i;
int maxRow = matrix.size();
int maxCol = matrix[0].size();
vector<int> b(maxCol, 0); //记录当前i~j行组成大矩阵的每一列的和，将二维转化为一维
int row,col;//临时记录左上角行列坐标
vector<int> pos(4);//记录左上角和右下角最终坐标
for (int i = 0; i < maxRow; i++) { //以i为上边，从上而下扫描
b.assign(maxCol, 0); //每次更换子矩形上边，就要清空b，重新计算每列的和
//子矩阵的下边往下移动变长，从i到maxROw-1，
for (int j = i; j < maxRow; j++) {
//已转换为求连续最大子序列和，一下就相当于求一次最大子序列和
dp_i = 0;
for (int k = 0; k < maxCol; k++) {
b[k] += matrix[j][k];
//我们只是不断增加其高，也就是下移矩阵下边，所有这个矩阵每列的和只需要加上新加的哪一行的元素
if (dp_i > 0) {
dp_i += b[k];
} else {
dp_i = b[k];
//新起一个点时保存这个点为临时左上角坐标
row=i;
col=k;
}
if(dp_i>maxsum)
{
maxsum=dp_i;
//更新最大子矩阵后更新最终左上角和右下角坐标
pos[0]=row;
pos[1]=col;
pos[2]=j;
pos[3]=k;
}
}
}
}
cout<<pos[0]<<" "<<pos[1]<<" "<<pos[2]<<" "<<pos[3]<<endl;
return maxsum;
}
};
int main() {
vector<vector<int>> matrix = {
{0, -2, -7, 0},
{9, 2, -6, 2},
{-4, 1, -4, 1},
{-1, 8, 0, -2}
};
Solution sol;
int maxSum = sol.getMaxMatrixSum(matrix);
cout << "子矩阵中和的最大值是: " << maxSum << endl;
return 0;
}
|
回溯算法（DFS）
回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，算法框架如下：
1
2
3
4
5
6
7
8
9
10
| result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
|
写 backtrack 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。
N皇后
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| /**
* @author: Juncker chan
* @date: 2024.10.24
* @details: n皇后问题
**/
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
vector<vector<string>> res;
bool isValid(vector<string> &board, int row, int col)
{
int n = board.size();
// 检查列是否有皇后互相冲突
for (int i = 0; i <= row; i++)
{
if (board[i][col] == 'Q')
{
return false;
}
}
// 检查右上方是否有皇后互相冲突
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
{
if (board[i][j] == 'Q')
{
return false;
}
}
// 检查左上方是否有皇后互相冲突
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
{
if (board[i][j] == 'Q')
{
return false;
}
}
return true;
}
// 路径：board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
void backTrack(vector<string> &board, int row)
{
// 触发结束条件
if (row == board.size())
{
res.push_back(board);
return;
}
int max_col = board[row].size();
for (int col = 0; col < max_col; col++)
{
if (!isValid(board, row, col))
continue;
// 做选择
board[row][col] = 'Q';
backTrack(board, row + 1);
board[row][col] = '.'; // 撤销选择
}
}
vector<vector<string>> solveNQueens(int n)
{
vector<string> board(n, string(n, '.'));
backTrack(board, 0);
return res;
}
};
int main()
{
Solution solution;
int n;
cout << "输入N: ";
cin >> n;
vector<vector<string>> results = solution.solveNQueens(n);
cout << "可能解如下:" << endl;
for (vector<string> &arrangement : results)
{
for (string &row : arrangement)
{
cout << row << endl;
}
cout << endl;
}
return 0;
}
|
动态规划的三个需要明确的点就是「状态」「选择」和「base case」，其实就对应着走过的「路径」，当前的「选择列表」和「结束条件」。
广搜算法（BFS）
单向BFS
BFS问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离。
这个广义的描述可以有各种变体，比如走迷宫，有的格子是围墙不能走，从起点到终点的最短距离是多少，如果加上这个迷宫带「传送门」可以瞬间传送的条件呢？比如说两个单词，要求你通过某些替换，把其中一个变成另一个，每次只能替换一个字符，最少要替换几次？再比如说连连看游戏，两个方块消除的条件不仅仅是图案相同，还得保证两个方块之间的最短连线不能多于两个拐点。你玩连连看，点击两个坐标，游戏是如何判断它俩的最短连线有几个拐点的？
本质上看这些问题都没有区别，就是一幅「图」，让你从一个起点，走到终点，问最短路径。这就是 BFS 的本质。
算法框架如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| int BFS(Node start, Node target) {
queue<Node> q;
set<Node> visited;
q.push(start);
visited.insert(start);
while (!q.empty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
Node cur = q.front();
q.pop();
if (cur == target)
return step;
for (Node x : cur.adj()) {
if (visited.count(x) == 0) {
q.push(x);
visited.insert(x);
}
}
}
}
// 如果走到这里，说明在图中没有找到目标节点
}
|
BFS 的核心数据结构：cur.adj() 泛指 cur 相邻的节点，比如说二维数组中，cur 上下左右四面的位置就是相邻节点；visited 的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要 visited。
双向BFS
传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止。不过双向 BFS 也有局限，因为你必须知道终点在哪里，如下图：
无论传统 BFS 还是双向 BFS，无论做不做优化，从 Big O 衡量标准来看，时间复杂度都是一样的，只能说双向 BFS 是一种 trick，算法运行的速度会相对快一点。
解开密码锁的最少次数
LeetCode752.打开转盘锁
分析题目，首先要思考设计一个算法，穷举所有可能的密码组合，其次才是考虑deadends 和 target 的限制**
总共有 4 个位置，每个位置可以向上转，也可以向下转，共8种可能。比如说从 "0000" 开始，转一次，可以穷举出 "1000", "9000", "0100", "0900"... 共 8 种密码。然后，再以这 8 种密码作为基础，对每个密码再转一下，穷举出所有可能…
这可以抽象成一幅图，每个节点有 8 个相邻的节点，又让你求最短距离，成功转化为BFS问题。
限制条件呢？只需要两个以哈希表为底层实现的无序集合记录visited和deads就可以了。
题解如下：
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| class Solution {
public:
int openLock(vector<string>& deadends, string target) {
// 记录需要跳过的死亡密码
unordered_set<string> deads(deadends.begin(), deadends.end());
// 记录已经穷举过的密码，防止走回头路
unordered_set<string> visited;
queue<string> q;
// 从起点开始启动广度优先搜索
int step = 0;
q.push("0000");
visited.insert("0000");
while (!q.empty()) {
int sz = q.size();
// 将当前队列中的所有节点向周围扩散
for (int i = 0; i < sz; i++) {
string cur = q.front(); q.pop();
// 判断是否到达终点
if (deads.count(cur))
continue;
if (cur == target)
return step;
// 将一个节点的未遍历相邻节点加入队列
for (int j = 0; j < 4; j++) {
string up = plusOne(cur, j);
if (!visited.count(up)) {
q.push(up);
visited.insert(up);
}
string down = minusOne(cur, j);
if (!visited.count(down)) {
q.push(down);
visited.insert(down);
}
}
}
// 在这里增加步数
step++;
}
// 如果穷举完都没找到目标密码，那就是找不到了
return -1;
}
// 将 s[j] 向上拨动一次
string plusOne(string s, int j) {
s[j] = s[j] == '9' ? '0' : s[j] + 1;
return s;
}
// 将 s[i] 向下拨动一次
string minusOne(string s, int j) {
s[j] = s[j] == '0' ? '9' : s[j] - 1;
return s;
}
};
|
二分查找（BinarySearch）
最常用的二分查找场景：寻找一个数、寻找左侧边界、寻找右侧边界。以下为最基础框架：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (...) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
}
|
小细节：$left + (right - left) / 2$ 就和 $(left + right) / 2$ 的结果相同，但是有效防止了 left 和 right 太大，直接相加导致溢出的情况。
最基本的二分查找算法：
1
2
3
4
5
6
7
| 因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid+1 和 right = mid-1
因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回
|
寻找左侧边界的二分查找：
1
2
3
4
5
6
7
8
| 因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid
因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界
|
寻找右侧边界的二分查找：
1
2
3
4
5
6
7
8
9
10
11
| 因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid
因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界
又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right，必须减一
|
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| int binary_search(vector<int>& nums, int target) {
int left = 0, right = nums.size()-1;
while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] == target) {
// 直接返回
return mid;
}
}
// 直接返回
return -1;
}
int left_bound(vector<int>& nums, int target) {
int left = 0, right = nums.size()-1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回，锁定左侧边界
right = mid - 1;
}
}
// 判断 target 是否存在于 nums 中
if (left < 0 || left >= nums.size()) {
return -1;
}
// 判断一下 nums[left] 是不是 target
return nums[left] == target ? left : -1;
}
int right_bound(vector<int>& nums, int target) {
int left = 0, right = nums.size()-1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回，锁定右侧边界
left = mid + 1;
}
}
// 由于 while 的结束条件是 right == left - 1，且现在在求右边界
// 所以用 right 替代 left - 1 更好记
if (right < 0 || right >= nums.size()) {
return -1;
}
return nums[right] == target ? right : -1;
}
|
模拟与密码类问题
Morse Mismatches Problem
UVA508：Morse Mismatches Problem
密码题中的模拟题，题目很长其实不算难，使用两个以哈希表为底层的字典存储映射即可，注释很详细。主要流程就是逐个匹配单词计算最小差异，根据最小差异的不同if_else出各种结果就行了。
题解如下：
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| /**
* @author: Juncker chan
* @date: 2024.10.28
* @details: Morse Mismatches Problem
**/
#include <bits/stdc++.h>
using namespace std;
map<char, string> morse_map; // 字符到摩尔斯电码的映射
map<string, string> word_dict; // 单词及其摩尔斯电码表示的字典
// 计算两个摩尔斯电码字符串 morse_input 和 morse_code 之间的差异
// 如果它们完全相同，返回0；如果 morse_input 是 morse_code 的前缀，返回长度差异；否则返回 INT_MAX
int calculate_diff(string& morse_input, string& morse_code) {
if (morse_input == morse_code) return 0; // 完全匹配
if (morse_input.size() > morse_code.size()) return INT_MAX; // 如果 `morse_input` 更长，不可能是前缀
if (morse_input == morse_code.substr(0, morse_input.size())) return morse_code.size() - morse_input.size(); // 前缀匹配
return INT_MAX; // 没有匹配
}
// 找到与给定摩尔斯电码 `morse_input` 最接近的匹配单词
string find_best_match(string& morse_input) {
string best_match = ""; // 存储最接近的匹配单词
int min_diff = INT_MAX; // 最小差异初始化为 "无穷大"
for (map<string, string>::iterator it = word_dict.begin(); it != word_dict.end(); ++it) {
int diff = calculate_diff(morse_input, it->second); // 计算当前摩尔斯电码的差异
// 如果已经发生两次完全匹配，返回 "!"
if (diff == 0 && min_diff == 0 && best_match.back() != '!') {
best_match += "!";
return best_match;
}
// 如果找到更接近或相同的匹配，更新 best_match
if (diff <= min_diff) best_match = it->first;
min_diff = min(diff, min_diff); // 更新最小差异
}
if (min_diff > 0) best_match += "?"; // 如果不是完全匹配，追加 "?"
return best_match;
}
int main() {
string morse_code, character;
vector<string> results; // 存储结果
// 读取字符到摩尔斯电码的映射
while (cin >> character && character != "*") {
cin >> morse_code;
morse_map[character[0]] = morse_code; // 存储每个字符的摩尔斯电码
}
// 构建单词及其摩尔斯电码表示的字典
while (cin >> morse_code && morse_code != "*") {
for (char ch : morse_code)
word_dict[morse_code] += morse_map[ch]; // 将单词中的每个字符转换为摩尔斯电码
}
// 读取摩尔斯电码输入并处理，存储结果
while (cin >> morse_code && morse_code != "*") {
results.push_back(find_best_match(morse_code)); // 存储每个结果
}
// 在输入完全读取后打印所有结果
for (string& result : results) {
cout << result << endl;
}
return 0;
}
|
总结与时空复杂度
BFS与DFS
DFS 也可以找最短路径，但是时间复杂度相对BFS高很多。DFS 实际上是靠递归的堆栈记录走过的路径，你要找到最短路径，肯定得把二叉树中所有树杈都探索完才能对比出最短的路径有多长，而 BFS 借助队列做到一次一步「齐头并进」，是可以在不遍历完整棵树的条件下找到最短距离的。
BFS 可以找到最短距离，但是空间复杂度高，而 DFS 的空间复杂度较低。
以处理二叉树问题为例，假设给你的这个二叉树是满二叉树，节点数为 $N$，对于 DFS 算法来说，空间复杂度无非就是递归堆栈，最坏情况下顶多就是树的高度，也就是$ O(logN)$。
但是你想想 BFS 算法，队列中每次都会储存着二叉树一层的节点，这样的话最坏情况下空间复杂度应该是树的最底层节点的数量，也就是 $N/2$，用 Big O 表示的话也就是 $O(N)$。
由此观之，BFS 还是有代价的，一般来说在找最短路径的时候使用 BFS，其他时候还是 DFS 使用得多一些（主要是递归代码好写）。
仅供参考，可能有误
