DFS从入门到精通

DFS从入门到精通

跳台阶

题目描述：

一个楼梯共有n级台阶，每次可以走一级或者两级，问从第0级台阶到第n级台阶一共有多少种方案。

输入格式：

共一行，包含一个整数n。

输出格式：

共一行，包含一个整数，表示方案数。

数据范围：

1≤n≤15

输入样例：

5

输出样例：

8

code：

#include <iostream>
using namespace std;
int main(){
   
    int n;
    int f[20];
    cin>>n;
    f[0]=1;
    for(int i=1;i<=n;i++){
   
        f[i]=f[i-1]+f[i-2];
    }
    cout<<f[n-1];
    return 0;
}

递归实现指数型枚举

题目描述：

从1∼n这n个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数n。

输出格式

每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。
对于没有选任何数的方案，输出空行。

数据范围

1≤n≤15

输入样例：

3

输出样例：

3
2
2 3
1
1 3
1 2
1 2 3

code：

#include<iostream>
using namespace std;
int n;
int st[20];//1表示不选这个数，2表示选这个数，0表示为初始状态
void dfs(int x){
   
    if(n==x){
   
        for(int i=0;i<n;i++)
            if(st[i]==2)
                cout<<i+1<<' ';
        cout<<endl;
        return ;
    }
    st[x]=1;
    dfs(x+1);
    st[x]=0;
    
    st[x]=2;
    dfs(x+1);
    st[x]=0;
}
int main(){
   
    cin>>n;
    dfs(0)