-
求两个串的最大公共子序列
此题要注意子序列和子串的概念。
假如两个串第一个位置的元素相同，那么只需比较两串剩余的部分的公共子序列长度。
如果不同，有两种情况：
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; }
