有关递归

p1478陶陶摘苹果https://www.luogu.org/problemnew/show/P1478

题意：苹果树上的每个苹果，会告诉苹果的高度已经主人摘它需要的最大力气。a是板凳高度，b是陶陶能伸的最大高度。题目告诉了开始时陶陶的力气s，求最多能摘多少苹果。

这道题解题方法之一是采用回溯法：我们不难发现，对于那些不能够采到的苹果，我们搜索它们只会白白浪费时间，那我们就可以将这些苹果排除掉，这样就使得搜索子树被缩小了。这就是剪枝。我们可以将所有的苹果按照高度从矮到高排序。在这种情况下当我们搜索到一个够不到的苹果时，无论我们再往下搜索多久，我们都不会再搜索到可以够得到的苹果了。这时候我们就可以return 0 了。

就会发现在输出的每次调用的函数中，有很多次调用的num和rest是相同的，这就说明我们做了很多无用功。那么怎么优化呢？这时候记忆化搜索就闪亮登场了：

所谓记忆化搜索，就是将每个不同参量的函数的返回值存在一个数组里，当再次调用这个函数的时候，就不用再次费时间计算这个函数的返回值了

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n,s;//苹果树数目，力气s
int a,b;//椅子告诉a,淘淘手伸直的最大高度b
//int x[5005],y[5005];//苹果树高度，需要力气
int vis[5005][1001],mem[5005][1001];//vis存储是否访问过调用这两个参量的函数,mem存储调用这两个参量的函数的返回值
struct apple
{
   int xi,yi;
}ap[5005];
bool cmp(apple x,apple y)
{
    return x.xi<y.xi;
}
int dfs(int index,int rest)
{
    if(index>=n||ap[index].xi>a+b||rest<=0)//当搜索到碰不到的苹果，就不用继续往下了
        return 0;
    if(vis[index][rest])
        return mem[index][rest];
    vis[index][rest]=1;
    int maxx=dfs(index+1,rest);
    if(ap[index].xi<=a+b&&rest>=ap[index].yi)
    {
        int t=dfs(index+1,rest-ap[index].yi)+1;
        maxx=t>maxx?t:maxx;
    }
    return mem[index][rest]=maxx;//先赋值再返回maxx

}
int main()
{
    scanf("%d%d",&n,&s);
    scanf("%d%d",&a,&b);
    for(int i=0; i<n; i++)
    {
        scanf("%d%d",&ap[i].xi,&ap[i].yi);
    }
    sort(ap,ap+n,cmp);

    cout<<dfs(0,s)<<endl;
    return 0;
}

p1149火柴棒等式https://www.luogu.org/problemnew/show/P1149

题意：给出n,代表总的火柴数目，求满足条件的'A+B=C’的有多少种。其中‘+‘和'-'就要花费4根火柴。

思路：这道题要采用回溯法，我开始对于大于10的数的火柴数目不知道怎么求，后来参考，a[i]=a[i%10]+a[i/10];这是一个很巧妙的写法。在写dfs的时候，要注意退出条件，就是tot>2时，说明已经选了3个了。在每一次循环时，要先判断n-a[i]是否大于等于0，如果小于了，则火柴数目不够。还要注意回溯。回到上一个状态。

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n,ans=0,b[4];
int a[1005]={6,2,5,5,4,5,6,3,7,6};
// a[0]=6,a[1]=2,a[2]=5,a[3]=5,a[4]=4,a[5]=5,a[6]=6,a[7]=3,a[8]=8,a[9]=6;
 void dfs(int tot)//sum代表选择火柴的总根数
 {
     if(tot>2)
        return;
     for(int i=0;i<=1000;i++)
     {

         //n=n-a[i];
         if(n-a[i]>=0)
         {

             b[tot]=i;
              n=n-a[i];
             if(tot==2)
             {
                 if(b[0]+b[1]==b[2]&&n==0)
                 {
                     ans++;
                     //return;
                 }
             }
             else
                dfs(tot+1);
             n=n+a[i];
         }
     }

 }
int main()
{


    cin>>n;
    n-=4;
   // dfs(0,0,0);
    for(int i=10;i<=1000;i++)
    {
        a[i]=a[i%10]+a[i/10];
    }
    dfs(0);
    cout<<ans<<endl;
    return 0;
}

p1036选数https://www.luogu.org/problemnew/show/P1036

从n个数中选k个数，只要k个数的和为素数，即满足条件，求满足条件（和为素数）的一共有多少个

解答：就是用dfs,注意循环条件和退出条件，关键部分我参考了别人的，我自己还是不会写，我太low了吧 

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//const int maxn=5e6+5;
int a[25];
int vis[25];
ll ans=0;
int n,k;
bool isPrime(ll num)
{
                 //两个较小数另外处理
                 if(num ==2|| num==3 )
                                 return 1 ;
                 //不在6的倍数两侧的一定不是质数
                 if(num %6!= 1&&num %6!= 5)
                                 return 0 ;
                 int tmp =sqrt( num);
                 //在6的倍数两侧的也可能不是质数
                 for(int i= 5;i <=tmp; i+=6 )
                                 if(num %i== 0||num %(i+ 2)==0 )
                                                 return 0 ;
                 //排除所有，剩余的是质数
                 return 1 ;
}
void dfs(int step,int sum,int cnt)
    {
        if(step==n||cnt==k)  //如果已经进行到了n+1次，或者是已经选了k个数
        {
            if(isPrime(sum) && cnt==k)  //如果sum为一个素数且已经选了k个数
                ans++;  //总方案书+1
            return;  //返回
        }
        dfs(step+1,sum+a[step],cnt+1);  //继续搜索，选择下一个数
        dfs(step+1,sum,cnt);  //继续枚举不选择下一个数的情况
        return;
    }

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    dfs(0,0,0);
    cout<<ans<<endl;
    return 0;
}