• 求两个串的最大公共子序列

  此题要注意子序列和子串的概念。

  假如两个串第一个位置的元素相同，那么只需比较两串剩余的部分的公共子序列长度。

  如果不同，有两种情况：

  ​ 1.比较字串A剔除第一个位置元素与字串B的公共子序列

  ​ 2.比较字串A和字串B剔除第一个位置元素的公共子序列

  取两种情况的最大值。

#include <bits/stdc++.h>
using namespace std;
//求两个串的最大公共子序列
int f(string s1, string s2)
{
    if(s1.size() == 0 || s2.size() == 0)
        return 0;
    if(s1[0] == s2[0])
        return f(s1.substr(1,s1.size()), s2.substr(1,s2.size())) + 1;//剩余部分
    else
        return max(f(s1.substr(1, s1.size()), s2), f(s1, s2.substr(1, s2.size())));
}
int main()
{
    string s1;
    string s2;
    cin>>s1>>s2;
    int k = f(s1, s2);
    cout<<k;
    return 0;
}

• 在n个球中，任意去取m个（不放回）， 求有多少种不同取法

  假设有一个特殊球，此球的状态只有两种：被取到和没有被取到。

  若被取到，那么只需在n-1个球中取m-1个球。

  若没有被取到，需在n-1个球中取m个球。

  #include <bits/stdc++.h>
  using namespace std;
  //在n个球中，任意去除m个（不放回）， 求有多少种不同取法
  int f(int n, int m)
  {
      if(n<m)
          return 0;
      if(n==m)
          return 1;
      if(m==0)
          return 1;
  
      return f(n-1,m-1) + f(n-1, m);  // 找一个特殊球
  }
  int main()
  {
      int n, m;
      cin>>n>>m;
      int k = f(n, m);
      cout<<k;
      return 0;
  }
  
  

• 求n个元素的全排列

  第一个位置n个元素都有可能，所以将第一个位置的元素与后面的每个元素进行交换。

  每交换一次，第一个位置的元素就确定了，然后将剩余的部分也进行全排列，进行同样操作。

  但是注意最后要再交换回来。

  #include <bits/stdc++.h>
  using namespace std;
  //求n个元素的全排列
  void f(string s, int k)
  {
      if(k==s.size())
      {
          cout<<s<<endl;
      }
     for(int i=k;i<s.size();i++)
     {
         char ch = s[k]; s[k] = s[i]; s[i] = ch; // 试探
         f(s, k+1);
         ch = s[k]; s[k] = s[i]; s[i] = ch; // 回溯
     }
  }
  int main()
  {
      string s;
    cin>>s;
      f(s, 0);
      return 0;
  }
  
  

• 求反转串

  #include <bits/stdc++.h>
  using namespace std;
  //求反转串：如,cba->abc
  string f(string s)
  {
      if(s.length() < 2)
          return s;
      return f(s.substr(1,s.size())) + s[0];
  }
  int main()
  {
      string s;
      cin>>s;
      cout<<f(s);
      return 0;
  }
  

• 计算杨辉三角第n层的第m个系数

  第m层第n的系数的值等于 第n-1层第m个系数+第n-1层第m-1个系数。

  如果n=0或者m=1，返回1.

  #include <bits/stdc++.h>
  using namespace std;
  //计算杨辉三角第n层的第m个系数，m和n都从0开始
  int f(int n, int m)
  {
      if(m==0)
          return 1;
      if(m==n)
          return 1;
      return f(n-1, m) + f(n-1, m-1);
  }
  int main()
  {
      int n,m;
      cin>>n>>m;
      cout<<f(n, m)<<endl;
      return 0;
  }
  

• 计算m个A，n个B可以有多少个不同排列

  从第一个位置开始，可能选A，也可能选B。

  如果选A，那么以后的位置需要排列m-1个A和n个B。

  如果选B，以后的位置需要排列n个A和n-1个B。

  #include <bits/stdc++.h>
  using namespace std;
  //计算m个A，n个B可以有多少个不同排列
  int f(int m, int n)
  {
      if(n==0 || m==0)
          return 1;
      return f(m-1, n) + f(m, n-1); 
  }
  int main()
  {
      int m, n;
      cin>>m>>n;
      cout<<f(m, n)<<endl;
      return 0;
  }
  

• 整数分划问题

  数组a用来保存分划的数

  k是当前的位置

  #include <bits/stdc++.h>
  using namespace std;
  //整数的分划问题
  void f(int n, int a[], int k)
  {
      if(n==0)
      {
          for(int i=0; i<k; i++)
              cout<<a[i]<<" ";
          cout<<endl;
          return ;
      }
  
      for(int i=n; i>0; i--)
      {
          if(k>0 && a[k-1]<i)
              continue;
          a[k] = i;
          f(n-i, a, k+1);
      }
  }
  int main()
  {
      int n;
      cin>>n;
      int a[100];
      f(n, a, 0);
      return 0;
  }
  
  

• 查账单

  err_sum：错误总金额

  cur_sum：前面元素的累加和

  k：当前要处理的元素位置

  b：对应a中元素是否是漏掉的

  #include <bits/stdc++.h>
  using namespace std;
  //查账单
  //输入第一行是有错的总金额
  //接下来是n，表示将要输入的明细账目的条数
  //再接下来是n行整数，分别表示每笔账目的数目
  //要求输出可能漏掉的金额组合
  
  int n; //账目条数
  void f(int err_sum, int *a, int k, int cur_sum, bool *b)
  {
      if(cur_sum > err_sum)
          return ;
      if(cur_sum == err_sum)
      {
          for(int i=0; i<n; i++)
              if(!b[i])
                  cout<<a[i]<<" ";
          cout<<endl;
          return ;
      }
      if(k >= n)
          return ;
  
      b[k] = false;
      f(err_sum, a, k+1, cur_sum, b); // 不加到错误账单中
  
      b[k] = true;
      cur_sum += a[k];
      f(err_sum, a, k+1, cur_sum, b); // 加到错误账单中
  
      b[k] = false; // 回溯
  }
  int main()
  {
  
      int err_sum;//保存有错的总金额
      int *a;//n条账目明细
      bool *b;
      cin>>err_sum>>n;
      a = new int[n];
      b = new bool[n];
      for(int i=0; i<n; i++)
          cin>>a[i];
      f(err_sum, a, 0, 0, b);
      return 0;
  }