搜索(重復子問題，邏輯相同)&記憶化(緩存數組緩存值)
三種遍歷：中先后(顧名思義即看根的順序)
點擊查看代碼
void dfs(int u) {
if(u > n) return ;
dfs(u + 1);
cout << u << endl;
dfs(u + 1);
}
形式是：終止條件 + 邏輯式
STL全排列：
next_permutation()
對于特定順序開始的全排列：預處理一次順序
點擊查看代碼
if(sum==0){//跑一遍起始順序
for(int i = a[k]; i <= n; ++ i){
if(!vis[i]){
vis[i] = 1;
f[k] = i;
dfs(k + 1);
vis[i] = 0;
}
}
}
else{//再往后續跑
for(int i = 1; i <= n; ++ i){
if(!vis[i]){
vis[i] = 1;
f[k] = i;
dfs(k + 1);
vis[i] = 0;
}
}
}
lambda自遞歸：lambda自遞歸
取路徑：關于取路徑
取方案：取方案
對于走迷宮問題的邊界判斷問題：
可以人為在邊界加一堵墻，來限定迷宮范圍
搜索：本質是重復子問題
將規模大的問題轉化為形式相同但規模更小的子問題，邏輯相同所以專注于實現本層的邏輯即可
且dfs(pos)含義：1···pos-1層已決定，現考慮第pos位情況
DFS：不斷嘗試更進一步，碰壁就回頭，換一條路繼續走
DFS答案會呈現出一顆搜索樹的形式
對于回溯： 本質是當前層有x種情況， 當前選擇一種， 對剩余x - 1種的考慮
取數：套用枚舉子集
點擊查看代碼
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int n, k, a[N], x[N], ans;
void check(int p) {
for(int x = 2; x * x <= p; ++ x) {
if(p % x == 0) {
return ;
}
}
++ ans;
}
void dfs(int pos) {
if(pos == n + 1) {
int sum = 0, cnt = 0;
for(int i = 1; i <= n; ++ i) {
cnt += a[i];
sum += a[i] * x[i];
}
if(cnt != k) return ;
check(sum);
return ;
}
for(int i = 0; i <= 1; ++ i) {
a[pos] = i;
dfs(pos + 1);
}
}
int main() {
cin >> n >> k;
for(int i = 1; i <= n; ++ i) {
cin >> x[i];
}
dfs(1);
cout << ans << endl;
return 0;
}
取數：正解
維護一個數時非必要添加參數，可用以取限制
點擊查看代碼
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int n, k, a[N], x[N], ans;
void check(int p) {
for(int x = 2; x * x <= p; ++ x) {
if(p % x == 0) {
return ;
}
}
++ ans;
}
void dfs(int pos) {
if(pos == k + 1) {
int sum = 0;
for(int i = 1; i <= k; ++ i) {
sum += x[a[i]];
}
check(sum);
return ;
}
for(int i = a[pos - 1] + 1; i <= n; ++ i) {//保證第pos位+1嚴格遞增
a[pos] = i;
dfs(pos + 1);
}
}
int main() {
cin >> n >> k;
for(int i = 1; i <= n; ++ i) {
cin >> x[i];
}
dfs(1);
cout << ans << endl;
return 0;
}
BFS(順序結構，有序性)：逐層擴展 BFS
BFS逐層擴展，所以當BFS搜索樹為去掉非最短路徑情況時會出現一棵最短路徑樹
隊列(First In First Out)：先存一步能到的點，然后再存兩步能到的點，再生成3步能到····，保證了離起點更近一定有先入隊
BFS其中的隊列優化，但其實本質是不用隊列而是形式上處于類似分裂思想
例如：
點擊查看代碼
如迷宮問題：
每次可以分裂為4個情況走到下一個點，且有先分裂一定有比后分裂離起點更近，后分裂一定比起點更遠
因BFS逐層擴展，所以當初次訪問在k層，意味著走k步可以到達這個點
BFS框架：
1.建隊
2.(非空時)將本層能拓展到的all點加入隊列，并彈出本層
剪枝
記憶化搜索
使程序更簡潔
DFS的兩種狀態表示形式：
全局變量存儲：
int sum = 0;
void dfs(int u) {
if(找到答案) {
輸出或統計 sum;
return;
}
for(枚舉下一步操作) {
if(合法操作) {
sum = sum + a[i];
dfs(u + 1);
sum = sum - a[i];//此時需要對sum回溯
}
}
}
函數參數存儲傳遞：
void dfs(int u, int sum) {
if(找到答案) {
輸出或統計 sum;
return;
}
for(枚舉下一步操作) {
if(合法操作) {
dfs(u + 1, sum + a[i]);//無須回溯
}
}
}
構造函數： 無賦值時為構造的默認值
STL容器中基本都包含構造函數，用來初始化STL
構造函數：
struct AK {
int x, y;
AK(int sx = 0, int sy = 0) {//構造函數與結構體同名，無須返回值
x = sx, y = sy;
}
}
調用:2種
AK tmp(1, 1);//在新創建的tmp中賦值即tmp.x和tmp.y
q.push(tmp);
//臨時變量
q.push(AK(1, 1));
浙公網安備 33010602011771號