递推与递归 \\ DFS深度优先搜索

原题单链接：洛谷题单 || 备用题单

递归先处理边界，再扩展子状态；枚举方案时注意回溯还原。以下示例各自独立编译。

跳台阶

每次走 1 或 2 阶；此整数实现要求 0≤n≤92。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n; vector<unsigned long long> f(max(2,n+1)); f[0]=f[1]=1;
    for(int i=2;i<=n;++i) f[i]=f[i-1]+f[i-2]; cout << f[n] << '\n';
}

递归实现指数型枚举

#include <bits/stdc++.h>
using namespace std;

int n; vector<int> a;
void dfs(int x) {
    if(x>n) { for(int v:a) cout << v << ' '; cout << '\n'; return; }
    dfs(x+1); a.push_back(x); dfs(x+1); a.pop_back();
}
int main() { cin >> n; dfs(1); }

递归实现排列型枚举

#include <bits/stdc++.h>
using namespace std;

int n; vector<int> a; vector<bool> used;
void dfs() {
    if((int)a.size()==n) { for(int v:a) cout << setw(5) << v; cout << '\n'; return; }
    for(int i=1;i<=n;++i) if(!used[i]) { used[i]=true; a.push_back(i); dfs(); a.pop_back(); used[i]=false; }
}
int main() { cin >> n; used.resize(n+1); dfs(); }

递归实现组合型枚举

#include <bits/stdc++.h>
using namespace std;

int n,r; vector<int> a;
void dfs(int start) {
    if((int)a.size()==r) { for(int v:a) cout << setw(3) << v; cout << '\n'; return; }
    for(int i=start;i<=n-(r-(int)a.size())+1;++i) { a.push_back(i); dfs(i+1); a.pop_back(); }
}
int main() { cin >> n >> r; dfs(1); }

P1036 选数

#include <bits/stdc++.h>
using namespace std;

int n,k,ans; vector<int> a;
bool prime(int x) { if(x<2) return false; for(int d=2;d<=x/d;++d) if(x%d==0) return false; return true; }
void dfs(int start,int cnt,int sum) {
    if(cnt==k) { ans+=prime(sum); return; }
    for(int i=start;i<=n-(k-cnt);++i) dfs(i+1,cnt+1,sum+a[i]);
}
int main() { cin >> n >> k; a.resize(n); for(auto &x:a) cin >> x; dfs(0,0,0); cout << ans << '\n'; }

十种配料（每种 1～3 份）

#include <bits/stdc++.h>
using namespace std;

int n; vector<int> a(10); vector<vector<int>> ans;
void dfs(int x,int sum) {
    if(sum+(10-x)>n || sum+3*(10-x)<n) return;
    if(x==10) { ans.push_back(a); return; }
    for(int i=1;i<=3;++i) { a[x]=i; dfs(x+1,sum+i); }
}
int main() { cin >> n; dfs(0,0); cout << ans.size() << '\n'; for(auto &v:ans) { for(int x:v) cout << x << ' '; cout << '\n'; } }

火星人：排列的后继

从给定排列向后推进 m 次，使用标准库避免枚举无关排列。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,m; cin >> n >> m; vector<int> a(n); for(auto &x:a) cin >> x;
    while(m--) next_permutation(a.begin(),a.end());
    for(int x:a) cout << x << ' ';
}

P1149 火柴棒等式

#include <bits/stdc++.h>
using namespace std;

int cost(int x) {
    static int c[]={6,2,5,5,4,5,6,3,7,6}; int s=0;
    do { s+=c[x%10]; x/=10; } while(x); return s;
}
int main() {
    int n,ans=0; cin >> n;
    for(int a=0;a<=1111;++a) for(int b=0;b<=1111;++b)
        if(cost(a)+cost(b)+cost(a+b)+4==n) ++ans;
    cout << ans << '\n';
}

配料：酸度乘积与苦度总和

#include <bits/stdc++.h>
using namespace std;

int n; long long ans=LLONG_MAX; vector<int> s,b;
void dfs(int x,long long product,long long sum,bool picked) {
    if(x==n) { if(picked) ans=min(ans,llabs(product-sum)); return; }
    dfs(x+1,product,sum,picked); dfs(x+1,product*s[x],sum+b[x],true);
}
int main() { cin >> n; s.resize(n); b.resize(n); for(int i=0;i<n;++i) cin >> s[i] >> b[i]; dfs(0,1,0,false); cout << ans << '\n'; }

P1135 奇怪的电梯

用最优步数剪枝；最短路通常更适合 BFS。

#include <bits/stdc++.h>
using namespace std;

int n,target; vector<int> k,dist;
void dfs(int x,int steps) {
    if(x<1 || x>n || steps>=dist[x]) return;
    dist[x]=steps; dfs(x+k[x],steps+1); dfs(x-k[x],steps+1);
}
int main() {
    int start; cin >> n >> start >> target; k.resize(n+1); dist.assign(n+1,INT_MAX);
    for(int i=1;i<=n;++i) cin >> k[i]; dfs(start,0); cout << (dist[target]==INT_MAX?-1:dist[target]) << '\n';
}

红与黑：四方向连通区域

#include <bits/stdc++.h>
using namespace std;

int w,h; vector<string> g;
int dfs(int x,int y) {
    if(x<0 || x>=h || y<0 || y>=w || g[x][y]=='#') return 0;
    g[x][y]='#'; return 1+dfs(x-1,y)+dfs(x+1,y)+dfs(x,y-1)+dfs(x,y+1);
}
int main() {
    while(cin >> w >> h && w && h) {
        g.resize(h); for(auto &s:g) cin >> s;
        for(int i=0;i<h;++i) for(int j=0;j<w;++j) if(g[i][j]=='@') cout << dfs(i,j) << '\n';
    }
}

P1596 Lake Counting

#include <bits/stdc++.h>
using namespace std;

int n,m; vector<string> g;
void dfs(int x,int y) {
    if(x<0 || x>=n || y<0 || y>=m || g[x][y]!='W') return;
    g[x][y]='.';
    for(int dx=-1;dx<=1;++dx) for(int dy=-1;dy<=1;++dy) if(dx || dy) dfs(x+dx,y+dy);
}
int main() {
    cin >> n >> m; g.resize(n); for(auto &s:g) cin >> s; int ans=0;
    for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(g[i][j]=='W') { ++ans; dfs(i,j); }
    cout << ans << '\n';
}

棋盘放置：不同行、不同列

#include <bits/stdc++.h>
using namespace std;

int n,k,ans; vector<string> g; vector<bool> used;
void dfs(int row,int cnt) {
    if(cnt==k) { ++ans; return; }
    if(row==n || cnt+n-row<k) return;
    dfs(row+1,cnt);
    for(int j=0;j<n;++j) if(g[row][j]=='#' && !used[j]) { used[j]=true; dfs(row+1,cnt+1); used[j]=false; }
}
int main() {
    while(cin >> n >> k && n!=-1) { g.resize(n); used.assign(n,false); for(auto &s:g) cin >> s; ans=0; dfs(0,0); cout << ans << '\n'; }
}

整数划分为 k 个正整数

#include <bits/stdc++.h>
using namespace std;

int n,k,ans;
void dfs(int start,int cnt,int sum) {
    if(cnt==k) { ans+=(sum==n); return; }
    for(int i=start;i<= (n-sum)/(k-cnt);++i) dfs(i,cnt+1,sum+i);
}
int main() { cin >> n >> k; dfs(1,0,0); cout << ans << '\n'; }

单词接龙

#include <bits/stdc++.h>
using namespace std;

int n,ans; vector<string> s; vector<int> used; vector<vector<int>> overlap;
void dfs(int x,int len) {
    ans=max(ans,len); ++used[x];
    for(int i=0;i<n;++i) if(used[i]<2 && overlap[x][i]) dfs(i,len+(int)s[i].size()-overlap[x][i]);
    --used[x];
}
int main() {
    cin >> n; s.resize(n); used.resize(n); overlap.assign(n,vector<int>(n)); for(auto &v:s) cin >> v; char start; cin >> start;
    for(int i=0;i<n;++i) for(int j=0;j<n;++j)
        for(int k=1;k<(int)min(s[i].size(),s[j].size());++k)
            if(s[i].substr(s[i].size()-k)==s[j].substr(0,k)) { overlap[i][j]=k; break; }
    for(int i=0;i<n;++i) if(s[i][0]==start) dfs(i,s[i].size()); cout << ans << '\n';
}