20算法周记之《代码随想录》图论（四）
学习小结
本周跟随代码随想录继续图论相关学习，主要聚焦于从一个点到另一个点的最小距离问题，学习了 dijkstra，bellman_ford，floyd，A* 算法。
相比于此前的算法设计课，更深刻地了解了各个算法的优势和缺点，比如 dijkstra 不能应对 负权 的边，bellman_ford可能会陷入负权回路的陷阱中，A* 不擅长多源距离等。
至此，代码随想录的一刷算是完成力，嘛，明天起就得开始狠狠二刷咯。
图论
dijkstra(朴素版)
题意：给一些节点和节点之间部分路径（有向），求起点到终点的最短路径是多少。
方法：其实bfs/dfs应该也行吧，dijkstra 是求一个点到其余点的最短路径距离。
本质和prim差不多，但prim只要关注点之间的距离就行，而dijkstra要考虑的可就多了，每次更新最短距离不仅要看新纳入点与当前体系的距离，还要看起点到体系边缘的距离。但是该方法不能对有负数权值的图使用，比如下面这个
从节点一出发，如果按照算法，走的路线是 1-3-4，最后看到1-2；但上帝视角可以看到，应该走 1-2-3-4。路线错误的原因是，该算法处理不了多段路程权值小于一段路程的情况。参考代码随想录思路的解法
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#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> grid(n+1, vector<int>(n+1, INT_MAX));
for (int i = 0; i < m; i++) {
int s, e, v;
cin >> s >> e >> v;
grid[s][e] = v;
}
vector<bool>visited(n+1, false);
vector<int>min_dist(n+1, INT_MAX);// 到各点最短距离
min_dist[1] = 0;// 起点到自己的距离为零
for (int i = 1; i < n; i++) {
// 寻找与当前节点最近的的节点
int cur = 1; // 默认第一个，解决初始化的问题
int closest_way = INT_MAX;
for (int i = 1; i <= n; i++) {
if (!visited[i] && min_dist[i] < closest_way) {
cur = i;
closest_way = min_dist[i];
}
}
// 加入访问列表中
visited[cur] = true;
// 更新最短距离
for (int i = 1; i <= n; i++) {
if (!visited[i] && grid[cur][i] != INT_MAX && min_dist[cur] + grid[cur][i] < min_dist[i]) {
min_dist[i] = min_dist[cur] + grid[cur][i];
}
}
}
if (min_dist[n] == INT_MAX) {
cout << -1 << endl;
}
else {
cout << min_dist[n] << endl;
}
return 0;
}dijkstra(堆优化版)
题意：与 [[dijkstra(朴素版)]]相同，都是求起点到终点最短距离
方法：此处重点阐述该方法与普通迪杰斯特拉的不同，在[[dijkstra(朴素版)]]中，每次都要遍历所有的边来选取与当前体系距离最短的点，堆优化则是引入了小顶堆来解决这个问题，小顶堆保持堆顶是所有边中最小的那个，每次只需要取堆顶即可。C++中通过优先级队列来实现小顶堆。
参考代码随想录思路的解法：
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#include <iostream>
#include <vector>
#include <climits>
#include <list>
#include <queue>
using namespace std;
class my_comparison {
public:
bool operator()(const pair<int, int> &lhs, const pair<int, int> &rhs) {
return lhs.second > rhs.second; // 队尾到队首降序，取出来就是升序
}
};
priority_queue<pair<int, int>, vector<pair<int,int>>, my_comparison> pq;
struct Edge {
int to;// 连接点号
int val; // 权值
Edge(int a, int b): to(a), val(b) {}
};
int main() {
int n, m;
cin >> n >> m;
vector<list<Edge>> grid(n+1);
// 初始化
for (int i = 0; i < m; i++) {
int from, to, val;
cin >> from >> to >> val;
grid[from].push_back(Edge(to, val));
}
vector<bool> visited(n+1, false);
vector<int> min_dist(n+1, INT_MAX);
// 初始化优先级队列
int start = 1;
int end = n;
pq.push(make_pair(start, 0));
min_dist[start] = 0;
// 开始算法
while(!pq.empty()) {
// 第一步，取到最近点，取优先级队列队首即可
pair<int, int> p = pq.top();
pq.pop();
// 去除已访问的点
if (visited[p.first]) continue;
// 标记取点成功
visited[p.first] = true;
// 开始遍历当前点所连接的其它点
for (Edge &e : grid[p.first]) {
if (!visited[e.to] && e.val + min_dist[p.first] < min_dist[e.to]) {
min_dist[e.to] = e.val + min_dist[p.first];
pq.push(make_pair(e.to, min_dist[e.to]));
}
}
}
if (min_dist[n] != INT_MAX) cout << min_dist[n] << endl;
else cout << "-1" << endl;
return 0;
}Bellman_ford算法应用
题意：本质是有向图中求起点到终点的最短路程，但是可能出现负权值的边
方法：由于有负权值的边，不能用迪杰斯特拉，这里就要用 Bellman_ford 算法，该算法本质是对每条边做 n-1 次的松弛，n是点的数量，松弛指的是根据其它点到该点的距离和权值取小值。与此前的最大不同在于，该算法专注于边，所以grid只要记录每条边的起点、终点和权值即可。详情可查看注释与代码。
但是，该算法不能解决负权回路的问题。
参考代码随想录思路的解法
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#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
// 初始化, 用于存储所有的边
vector<vector<int>> grid;
for (int i = 0; i < m; i++) {
int s, t, v;
cin >> s >> t >> v;
grid.push_back({s, t, v});
}
// 建立最小距离
// 对m条边各做n-1次松弛
vector<int> min_dist(n+1, INT_MAX);
min_dist[1] = 0;
// 之所以要n-1次，是因为1次松弛能获取起点到该点通过一条边的最小值
// 每多松弛一次就能多通过一个边
// n-1 是处理一长条的极端情况
for (int i = 1; i < n; i++) { // n-1次松弛
for (auto &e : grid) {
int from = e[0];
int to = e[1];
int val = e[2];
if (min_dist[from] == INT_MAX) continue; // 该情况说明起点尚未连通
if (min_dist[to] > min_dist[from] + val) { // 松弛就是更新小值
min_dist[to] = min_dist[from] + val;
}
}
}
if (min_dist[n] == INT_MAX) cout << "unconnected" << endl;
else cout << min_dist[n] << endl;
return 0;
}Bellman_ford队列优化算法（SPFA）应用
题意，与 [[Bellman_ford算法应用]]一样，都是在无负权回路的情况下，求起点到终点的最短路径长度。
方法，顾名思义，SPFA通过队列一定程度上减少了松弛的次数，在原先的 Bellman_ford算法中，每条边必须要经过 n-1 次松弛，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#include <iostream>
#include <vector>
#include <climits>
#include <list>
#include <queue>
using namespace std;
struct Edge {
int to; // 目标
int val; // 权值
Edge(int a, int b): to(a), val(b) {}
};
int main() {
// 初始化
int n, m;
cin >> n >> m;
vector<list<Edge>> grid(n+1);
for (int i = 0; i < m; i++) {
int s, t, v;
cin >> s >> t >> v;
grid[s].push_back(Edge(t,v));
}
vector<bool> is_in_queue(n+1, false);
queue<int> q;// 待松弛边
vector<int> min_dist(n+1, INT_MAX);
q.push(1);
is_in_queue[1] = true;
min_dist[1] = 0;
while(!q.empty()) {
int node = q.front();
q.pop();
for (const Edge &e : grid[node]) {
min_dist[e.to] = min(min_dist[e.to], min_dist[node]+e.val);
if (!is_in_queue[e.to]) { // 成功松弛就准备遍历目标点
q.push(e.to);
is_in_queue[e.to] = true;
}
}
is_in_queue[node] = false;
}
if (min_dist[n] == INT_MAX) cout << "unconnected" << endl;
else cout << min_dist[n] << endl;
return 0;
}Bellman_ford判断负权回路
题意，与 [[Bellman_ford算法应用]]类似，但是现在会出现负权回路。
方法，要解决负权回路，就要知道一点，在传统的Bellman_ford算法中，每条边最多 n-1 次松弛即可获取结果，此后再多的松弛也不会改变结果。所以，如果一条边松弛次数达到 n 次，说明存在负权回路。
而对于队列优化版的 Bellman_ford 算法，每个点最多进入队列 n-1 次，毕竟每次进队列，都是因为某条连着这个点的边被成功松弛，如果次数到达 n，也说明存在负权回路。
普通Bellman_ford判断负权回路
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#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
// 初始化, 用于存储所有的边
vector<vector<int>> grid;
for (int i = 0; i < m; i++) {
int s, t, v;
cin >> s >> t >> v;
grid.push_back({s, t, v});
}
// 建立最小距离
// 对m条边各做n-1次松弛
vector<int> min_dist(n+1, INT_MAX);
min_dist[1] = 0;
bool circle_flag = false;
// 之所以要n-1次，是因为1次松弛能获取起点到该点通过一条边的最小值
// 每多松弛一次就能多通过一个边
// n-1 是处理一长条的极端情况
for (int i = 1; i <= n; i++) { // n-1次松弛，最后一次用来判断负权回路
for (auto &e : grid) {
int from = e[0];
int to = e[1];
int val = e[2];
if (min_dist[from] == INT_MAX) continue; // 该情况说明起点尚未连通
if (min_dist[to] > min_dist[from] + val) { // 松弛就是更新小值
if (i < n) {
min_dist[to] = min_dist[from] + val;
}
else {
circle_flag = true;
break;
}
}
}
if (circle_flag) break;
}
if (circle_flag) cout << "circle" << endl;
else if (min_dist[n] == INT_MAX) cout << "unconnected" << endl;
else cout << min_dist[n] << endl;
return 0;
}SPFA判断负权回路
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#include <iostream>
#include <vector>
#include <climits>
#include <list>
#include <queue>
using namespace std;
struct Edge {
int to; // 目标
int val; // 权值
Edge(int a, int b): to(a), val(b) {}
};
int main() {
// 初始化
int n, m;
cin >> n >> m;
vector<list<Edge>> grid(n+1);
for (int i = 0; i < m; i++) {
int s, t, v;
cin >> s >> t >> v;
grid[s].push_back(Edge(t,v));
}
vector<bool> is_in_queue(n+1, false);
queue<int> q;// 待松弛边
vector<int> min_dist(n+1, INT_MAX);
bool circle_flag = false;
vector<int> count_release(n+1, 0);
q.push(1);
is_in_queue[1] = true;
min_dist[1] = 0;
while(!q.empty()) {
int node = q.front();
q.pop();
for (const Edge &e : grid[node]) {
min_dist[e.to] = min(min_dist[e.to], min_dist[node]+e.val);
if (!is_in_queue[e.to]) {
q.push(e.to);
is_in_queue[e.to] = true;
count_release[e.to]++;
if(count_release[e.to] == n) {
circle_flag = true;
while(!q.empty()) q.pop();
break;
}
}
}
is_in_queue[node] = false;
}
if (circle_flag) cout << "circle" << endl;
else if (min_dist[n] == INT_MAX) cout << "unconnected" << endl;
else cout << min_dist[n] << endl;
return 0;
}Bellman_ford之单源有限最短路
题意：在 [[Bellman_ford判断负权回路]]的基础上，加上了最多经过 k 个节点的限制。
方法：两个重点
- 经过 k 个节点的本质是，对每条边最多k+1次松弛。因为每次松弛就能让起点向外多延申一边；
- 其实以往的 Bellman_ford 的实现中，对所有边遍历 n-1 次后，实际上很可能有边超过了 n-1 次松弛。比如 1 与 3 本没有直接连接，但由于对 1 与 2 的连接，使得 min_dist[3] 可以推出。换句话，就是用了本次遍历的结果推出本应下次遍历的结果。之所以之前的题目都没问题，是因为之前的题目中边松弛过多对结果没有影响。解决方法就是每次遍历时记录上一次的遍历结果，基于这个结果来松弛。
参考代码随想录思路的解法
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// 版本一
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;
int main() {
int src, dst,k ,p1, p2, val ,m , n;
cin >> n >> m;
vector<vector<int>> grid;
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
// p1 指向 p2，权值为 val
grid.push_back({p1, p2, val});
}
cin >> src >> dst >> k;
vector<int> minDist(n + 1 , INT_MAX);
vector<int> minDist_copy(n+1);// 记录上一次遍历结果
minDist[src] = 0;
for (int i = 1; i <= k + 1; i++) { // 对所有边松弛 k + 1次
minDist_copy = minDist;
for (vector<int> &side : grid) {
int from = side[0];
int to = side[1];
int price = side[2];
if (minDist_copy[from] != INT_MAX && minDist[to] > minDist_copy[from] + price) minDist[to] = minDist_copy[from] + price;
}
}
// for (int i = 0; i <=n; i++) {
// cout << minDist[i] << " ";
// }
// cout << endl;
if (minDist[dst] == INT_MAX) cout << "unreachable" << endl; // 不能到达终点
else cout << minDist[dst] << endl; // 到达终点最短路径
}Floyd算法应用
题目：给一个无向图，要求给出任意起点终点，能够输出存在的最短的路线的长度。
方法：这是多源最短路径求解，之前的 [[dijkstra(朴素版)]]和 [[Bellman_ford算法应用]]都是单源最短路径。Floyd算法不要求边的正负值，其中心思想是动态规划。建立三维数组，dp[i][j][k] val 的含义是，节点 i 到 j 经过 [1,k]的中间节点的最短值为 val。只要从0遍历到 k 层，就能获取所有点到其它点的最短路径。
但是要注意遍历方向，如果去数组按 dp[i][j][k]，那么k的循环必须在最外面一层，而 i 和 j 的顺序无关系。因为初始化时在 dp[i][j][0] 初始化的，必须由 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#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n+1, vector<int>(n+1, 10002)));
// dp[i][j][k] val 的含义是，节点 i 到 j 经过 [1,k]的中间节点的最短值为 val
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
dp[u][v][0] = w;
dp[v][u][0] = w; // 无向图
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j][k] = min(dp[i][j][k-1], dp[i][k][k-1] + dp[k][j][k-1]);
}
}
}
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int s, e;
cin >> s >> e;
if (dp[s][e][n] == 10002) cout << -1 << endl;
else cout << dp[s][e][n] << endl;
}
return 0;
}A*算法应用
题意：给一个起点和终点，从起点只能按一定规则移动，本题走 日（象棋中马的走法），求最短步数。
方法：bfs能解决，但时间消耗比较大，这里就要引入 A* 算法。实际上，A*算法没有定式，本质是 bfs，迪杰斯特拉 等算法的优化，其灵魂在于启发函数，通过这个函数指导高效遍历。
拿本体来说，在 bfs 的基础上，引入优先级队列和启发函数，启发函数用欧拉距离（也可用其它距离表示）衡量目前的点与目标点距离，优先选择离目标更近的点遍历。具体动画可看：A* && BFS
不过，A* 也有缺点，那就是不能像迪杰斯特拉一样对多个点都有遍历距离。如此看来，A*更适合于有明确信息指向目的地且只要单源的情况。
此外，陆爻齐突发奇想，如果点到起点也用启发函数衡量距离会怎样，结果当然有误。其原因在于，对节点统一衡量为 5，相当于对节点有层数的划分。如果也换启发函数，那么算法会趋近于走两点之间连线的点，这不一定是最佳路线，因为有走法规则限制。比如（5，2）和（5，4），在这个错误方法下要可能会走4步才能到。
参考代码随想录思路的解法
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#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
int a1, a2, b1, b2;
int dr[8][2] = {1, 2, 2, 1, 2, -1, 1, -2, -1, -2, -2, -1, -2, 1, -1, 2};
int moves[1001][1001];
struct Knight {
int x, y;
int g, h, f; // f = g + h
Knight(int a, int b) : x(a), y(b) {}
Knight() {}
bool operator < (const Knight &o) const{ return o.f < this->f; }
};
priority_queue<Knight> que;
int dis2begin(Knight &k) {
return (k.x - a1) * (k.x - a1) + (k.y - a2) * (k.y - a2);
}
int dis2end(Knight &k) {
return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2);
}
void bfsastar(Knight &k) {
Knight cur, next;
que.push(k);
while(!que.empty()) {
cur = que.top(); que.pop();
if (cur.x == b1 && cur.y == b2) {
break;
}
for (int i = 0; i < 8; i++) {
next.x = cur.x + dr[i][0];
next.y = cur.y + dr[i][1];
if (next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000) {
continue;
}
if (!moves[next.x][next.y]) {
moves[next.x][next.y] = moves[cur.x][cur.y] + 1;
// 计算f
//next.g = dis2begin(next);
next.g = cur.g + 5;
next.h = dis2end(next);
next.f = next.g + next.h;
que.push(next);
}
}
}
}
int main() {
int n;
cin >> n;
while (n--) {
memset(moves, 0, sizeof(moves));
cin >> a1 >> a2 >> b1 >> b2;
Knight k(a1, a2);
k.g = 0;
k.h = dis2end(k);
k.f = k.h;
bfsastar(k);
while(!que.empty()) que.pop();
cout << moves[b1][b2] << endl;
}
return 0;
}
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！
相关推荐
2024-11-17
【Weekly Algorithm】算法周记之《代码随想录》动态规划（一）
学习小结本周跟随《代码随想录》开始学习动态规划的相关题目，从基础的斐波那契数到爬楼梯，再到 01 背包问题，慢慢熟悉动态规划的五步法。《代码随想录》还提醒，调试重点是检查递推公式是否举例，检查打印 dp 数组是否和自己设想一致。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 此外除了寻常的二维数组动态规划，也尝试做滚动数组的练习。 动态规划 斐波那契数 题意，给一个数字 n，求斐波那契数中的第 n 个数 方法，虽然就算不看代码随想录也能轻易写出，但简单题的重点在于熟悉套路方法，下面按五步分析 确定 dp 数组及其下标含义，这里的 dp[i] 代表斐波那契数中的第 i 个数 确认递推公式，题目给出 dp[i]=dp[i-1]+dp[i-2] dp 数组初始化，题目也给出dp[0]=0;dp[1]=1; 确定遍历顺序，从递推公式可见，就是从前向后（0-n）遍历 举例推导 dp 公式，0 1 1 2 3 5 8 13 21 …… 陆爻齐的解 1234567891011121314class...
2024-11-24
【Weekly Algorithm】算法周记之《代码随想录》动态规划（二）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，由于期末月的到来，以及题目难度的增加，暂且将动态规划的学习进度放慢一点。下面继续巩固五步法。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 只能感叹，这动态规划真是一百道题才入门啊。 动态规划 分割等和子集 代码随想录 416. 分割等和子集 - 力扣（LeetCode） 题意，给一个数组，返回判断该数组是否能平分为和相等的两部分 方法，直觉上，可以用回溯遍历树，找到那个子节点，但复杂度太高。本题其实就是 01 背包的应用，nums[i] 本身，是物品，重量，以及价值。数组能否平分和的本质，就是平分和的大小的背包能否被刚好装满，也就是下标与值相等。 参考代码随想录思路的代码 1234567891011121314151617class Solution {public: bool canPartition(vector<int>& nums) { int sum =...
2024-12-01
【Weekly Algorithm】算法周记之《代码随想录》动态规划（三）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，主要是完全背包的入门，体会其与 01 背包的不同与关联。 下周两门考试，教务脑子真是进了水，搞这么紧干嘛。 动态规划 完全背包理论 代码随想录 52. 携带研究材料（第七期模拟笔试） 题目，与 [[01背包理论]]的差别在于一个物品可携带多次，求最大价值 方法， dp[j]，在遍历物品时，截止到空间为 j，可装入的最大价值 递推公式，dp[j]=max(dp[j],dp[j-weigh[i]]+val[i]) 初始化，全 0 遍历方向，重点，这是与 01 背包区别最大的地方，01 的滚动数组强调倒序遍历就是为了避免重复，在完全背包中，恰恰需要正序从而利用重复装入物品 举例，…… 参考代码随想录思路的解法 12345678910111213141516171819202122232425262728#include <iostream>#include <vector>using namespace std;int main() { int n, v; ...
2024-12-15
【Weekly Algorithm】算法周记之《代码随想录》动态规划（五）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学会了完全背包的应用，多重背包的理论，打劫打家劫舍问题，和股票买卖问题的入门版。认识到了所存储的状态并不只有 整数 这一种形式，还能有多个整数并成的 vector 作为状态使用。 不得不说，动态规划十分的灵活，一百道题入门还不是说说而已啊。 动态规划 完全平方数 代码随想录 279. 完全平方数 - 力扣（LeetCode） 题意，给一个整数 n，求其被完全平方数组成的最小个数。 方法，就是[[零钱兑换II]]的变体，给的零钱变成了自己找小于 n 的完全平方数，背包容量为 n dp[j] 含义为 在背包容量为 j 的情况下，完全平方数的最小组合 递推公式，dp[i]=min(dp[i],dp[i-j*j]+1)，也就是要么保持不变，要么就在已有的组合上加一 初始化，dp[0]=0,这是为了递推公式才这么初始化，也能理解，完全平方数不算...
2025-01-12
【Weekly Algorithm】算法周记之《代码随想录》动态规划（六）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学习完买卖股票相关内容，并初步探索子序列的部分。 买卖股票的题有明显的状态转换，但子序列就没那么明显。 动态规划 买卖股票的最佳时机II 代码随想录 122. 买卖股票的最佳时机 II - 力扣（LeetCode） 题意，在[[买卖股票的最佳时机]]的基础上，要求可以多次购买股票，但同一时段只能持有一支股票，也就是再卖出上一支股票前，不允许购入下一支股票。 方法，与[[买卖股票的最佳时机]]的差别，在于考虑购入当前股票时，是在上一支股票考虑购入和卖出的两个情况中取最大，并非直接取历史最便宜股票和当前股票对比。 参考代码随想录思路解法 123456789101112131415161718class Solution {public: int maxProfit(vector<int>& prices) { // dp[i][0] 考虑第i支股票时，考虑买入的情况；dp[i][1] 考虑第i支股票时，卖出的情况 int len =...
2025-02-09
【Weekly Algorithm】算法周记之《代码随想录》单调栈和图论（一）
学习小结本周跟随《代码随想录》学习关于单调栈的知识，同时开启图论。 单调栈通过保持一个栈从栈顶到栈底的递增或是递减序列，来解决找一个元素左/右的“第一个”更大/更小元素。 图论则是初窥dfs的门路，虽然道理一年前早在算法课学过考过，但现在也得复习才能捡回来。 单调栈 每日温度 代码随想录 739. 每日温度 - 力扣（LeetCode） 题意：给一个整数数组，求每个数字右侧比该数字更大的间距 方法：暴力解法就是O(n^2)的遍历。更高效率的方法是使用单调栈，所谓的单调栈就是从栈顶到栈底递增或递减的，如此排列，就能方便找任意元素的左右第一个更大更小的元素。 比如本题是找右边更大的，那么遍历数组时，遇到更小或相等的元素就直接入栈，而遇到更大的元素就弹栈，直到触底或碰到大元素再入栈，其中弹栈的元素就能记录本元素的下标与当时元素下标之差。 参考代码随想录思路的解法 12345678910111213141516171819202122232425class Solution {public: vector<int>...
系列文章