递归与递推+简单dfs

821. 跳台阶

题解：这个题目只需要会递归就行算是一道非常入门的递归问题

#include<iostream>

using namespace std;

int fib(int n)
{
    if(n<2) return 1;
    else return fib(n-1)+fib(n-2);
}

int main()
{
    int n;
    cin>>n;
    
    int ans=fib(n);
    
    cout<<ans<<endl;
    return 0;
}

92. 递归实现指数型枚举

#include<iostream>

using namespace std;

int n;
int st[16];

void dfs(int x)
{
    
    //结束递归的条件
    if(x>n)
    {
        for(int i=1;i<=n;i++)
        {
            if(st[i]==1) cout<<i<<" ";
        }
        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(1);
    
    return 0;
}

93. 递归实现组合型枚举

#include<iostream>

using namespace std;

int n,m;
int st[26];
int push[26];

void dfs(int x,int start)
{
    
    if(x>m)
    {
        for(int i=1;i<=m;i++)
        {
            cout<<st[i]<<" ";
        }
        cout<<endl;
        return;
    }
    
    
    for(int i=start;i<=n;i++)
    {
        st[x]=i;
        dfs(x+1,i+1);
        st[x]=0;
    }
}

int main()
{
    cin>>n>>m;
    dfs(1,1);
    return 0;
}

94. 递归实现排列型枚举

#include<iostream>

using namespace std;

int n;
int st[16];
int push[16];

void dfs(int x)
{
    if(x>n)
    {
        for(int i=1;i<=n;i++) cout<<push[i]<<' ';
        cout<<endl;
        return;
    }
    
    for(int i=1;i<=n;i++)
    {
        if(st[i]==0)
        {
            push[x]=i;
            st[i]=1;
            dfs(x+1);
            st[i]=0;
        }
    }
}

int main()
{
    cin>>n;
    
    dfs(1);
    
    return 0;
}

P1036 [NOIP2002 普及组] 选数

#include<iostream>
#include<cstdio>

using namespace std;

int n,k;
int push[30];
int st[30];
int res=0;

bool is_prime(int sum)
{
    if(sum<2) return false;
    for(int i=2;i<=sum/i;i++)
    {
        if(sum%i==0) return false;
    }
    return true;
}

void dfs(int x,int start)
{
    if(x>k)
    {
        int sum=0;
        for(int i=1;i<=k;i++) 
        {
            sum+=push[i];
        }
        if(is_prime(sum)) res++;
        return ;
    }

    for(int i=start;i<=n;i++)
    {
        push[x]=st[i];
        dfs(x+1,i+1);
        push[x]=0;
    }
    
}


int  main()
{
    cin>>n>>k;
    
    for(int i=1;i<=n;i++) cin>>st[i];
    
    dfs(1,1);
    
    cout<<res<<endl;
    
    return 0;
}

后面有时间就写题解 晚安。