递归与递推
求解递推问题：
1）把大问题细分成子问题，子问题的求解逻辑跟大问题是一样的；（递推式）（起始条件） 2）终止条件：就是细分到最小的那个最小的条件 递推加法原理： 如果有一件事有n类方法，第一类有a1种方法，第二类有a2种方法，……第n类有an种方法，则这件事的方法总数为：a1+a2……+an
P1255 数楼梯
#include<cstdio>//调用 scanf和printf 库
#include<cstring>//调用 memset 库
int n,ns=1;
int a[5010],b[5010],c[5010];
//定义
//注意数组大小
void Fibonacci()
//开始
{
a[1]=1,b[1]=2;//注意初始化
for(int i=3;i<=n;i++)//从第3个循环
{
for(int j=1;j<=ns;j++)c[j]=a[j]+b[j];//相加
for(int j=1;j<=ns;j++)//进位
{
if(c[j]>9)//大于9才进
{
c[j+1]+=c[j]/10;
c[j]%=10;
if(j+1>ns)ns++;//小心要多留一位
}
}
for(int j=1;j<=ns;j++)a[j]=b[j];
for(int j=1;j<=ns;j++)b[j]=c[j];
//交换
}
}
int main()
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
//清 0 优化
scanf("%d",&n);//输入
if(n<3)//小于 3 要多加小心----------卡了我两次
{
printf("%d",n);
return 0;
}
Fibonacci();
//高精和递推合并
for(int i=ns;i>0;i--)printf("%d",b[i]);
//逆序输出
return 0;//再见
}
P1002 [NOIP2002 普及组] 过河卒
#include<iostream>
using namespace std;
const int N=30;
//vis[i][j]如果是true代表点（i，j）的 控制点，flase则代表不是
bool vis[N][N];//全局数组，默认代表初始化为flase
long long a[N][N];//a[i][j]：zu 从点（0，0）到点（i，j）的方案数
int dx[9]={0,2,1,-1,-2,-2,-1,1,2};
int dy[9]={0,1,2,2,1,-1,-2,-2,-1};
int main(){
// 一行四个正整数，分别表示 B 点坐标和马的坐标。
int n,m;//B点坐标，终点
int x,y;//吗的坐标
cin>>n>>m>>x>>y;
//设置吗控制的点为不能走的点
// vis[x][y]=true;
// vis[x+2][y+1]=true;
// vis[x+1][y+2]=true;
// vis[x-1][y+2]=true;
// vis[x-2][y+1]=true;
// vis[x-2][y-1]=true;
// vis[x-1][y-2]=true;
// vis[x+1][y-2]=true;
// vis[x+2][y-1]=true;
//
for(int i=0;i<9;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
vis[nx][ny]=true;
}
//初始条件
//第0行（列：0-m)
for(int j=0;j<=m;j++){
// if(vis[0][j]==false)
if(!vis[0][j]) a[0][j]=1;//不是马的控制点，方案数为1
else break;//ma 的控制点（控制点同行的点都走不了），退出
}
//第0列（行：0-n）
for(int i=0;i<=n;i++)
{
if(!vis[i][0])a[i][0]=1;//不是马的控制点，方案数为1
else break;//ma 的控制点（控制点同列的点都走不了），退出
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{ //加法原理
if(!vis[i][j])a[i][j]=a[i-1][j]+a[i][j-1];
}
}
cout<<a[n][m]<<endl;
return 0;
}
3用上二维数组
#include<iostream>
using namespace std;
const int N=30;
//vis[i][j]如果是true代表点（i，j）的 控制点，flase则代表不是
bool vis[N][N];//全局数组，默认代表初始化为flase
long long a[N][N];//a[i][j]：zu 从点（0，0）到点（i，j）的方案数
//int dx[9]={0,2,1,-1,-2,-2,-1,1,2};
//int dy[9]={0,1,2,2,1,-1,-2,-2,-1};
int dir[9][2]={{0,0},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}} ;
int main(){
// 一行四个正整数，分别表示 B 点坐标和马的坐标。
int n,m;//B点坐标，终点
int x,y;//吗的坐标
cin>>n>>m>>x>>y;
//1.设置吗控制的点为不能走的点
// vis[x][y]=true;
// vis[x+2][y+1]=true;
// vis[x+1][y+2]=true;
// vis[x-1][y+2]=true;
// vis[x-2][y+1]=true;
// vis[x-2][y-1]=true;
// vis[x-1][y-2]=true;
// vis[x+1][y-2]=true;
// vis[x+2][y-1]=true;
// 2.
//for(int i=0;i<9;i++)
//{
// int nx=x+dx[i];
// int ny=y+dy[i];
// vis[nx][ny]=true;
//}
//3.二维数组方法
for(int i=0;i<9;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx>=0&&ny>=0)vis[nx][ny]=true;
}
//初始条件
//第0行（列：0-m)
for(int j=0;j<=m;j++){
// if(vis[0][j]==false)
if(!vis[0][j]) a[0][j]=1;//不是马的控制点，方案数为1
else break;//ma 的控制点（控制点同行的点都走不了），退出
}
//第0列（行：0-n）
for(int i=0;i<=n;i++)
{
if(!vis[i][0])a[i][0]=1;//不是马的控制点，方案数为1
else break;//ma 的控制点（控制点同列的点都走不了），退出
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{ //加法原理
if(!vis[i][j])a[i][j]=a[i-1][j]+a[i][j-1];
}
}
cout<<a[n][m]<<endl;
return 0;
}
代码2：
#include<bits/stdc++.h>
using namespace std;
int n,a[5005]={1},b[5005]={1},c[5005]={1},len=1;
//高精度加法
void f(){
int jw=0;//进位
for(int i=0;i<len;i++)
{
c[i]=a[i]+b[i]+jw;
jw=c[i]/10;
c[i]=c[i]%10;
}
if(jw!=0){
c[len]=jw;
len++;
}
for(int i=0;i<len;i++){
a[i]=b[i];
b[i]=c[i];
}
}
int main(){
cin>>n;
for(int i=2;i<=n;i++){
f();//调用高精度加法
}
for(int i=len-1;i>=0;i--){
cout<<c[i];//输出值
}
return 0;
}
P1044 [NOIP2003 普及组] 栈
#include<bits/stdc++.h>
using namespace std;
int f[20][20],n;
int main(){
cin>>n;
//第一个数i，表示的是未进栈
// 第二个事数j，表示栈内的数
for(int j=0;j<20;j++){
f[0][j]=1;//因为最后都会分成f[0][j]=1,1种情况的时候
}
for(int i=1;i<20;i++)
{
for(int j=0;j<20;j++){
if(j==0)f[i][j]=f[i-1][j+1];
else{
f[i][j]=f[i][j-1]+f[i-1][j+1];
}
}
}
cout<<f[n][0];//n个数没有进栈，栈内有0个数的情况。
return 0;
}
P1028 [NOIP2001 普及组] 数的计算
#include<iostream>
using namespace std;
const int N=1e3+10;
int f[N];//f[i]:i处理后具有该性质的个数
int main(){
int n;
cin>>n;
f[1]=1;
for(int i=1;i<=n;i++)
{
f[i]=1;//i自己
for(int j=1;j<=i/2;j++)
{
f[i]+=f[j];
}
}
cout<<f[n];
return 0;
}
P1464 Function
1 1 1
2 2 2
-1 -1 -1
输出
w(1, 1, 1) = 2
w(2, 2, 2) = 4
#include<bits/stdc++.h>
using namespace std;
long long dfs(long long a,long long b,long long c)
{ if(a<=0||b<=0||c<=0)return 1;
if(a>20||b>20||c>20)return dfs(20,20,20);
if(a<b&&b<c)return dfs(a,b,c-1)+dfs(a,b-1,c-1)-dfs(a,b-1,c);
return dfs(a-1,b,c)+dfs(a-1,b-1,c)+dfs(a-1,b,c-1)-dfs(a-1,b-1,c-1);
}
void lesson1()
{
long long a,b,c;
while(cin>>a>>b>>c){//只要一直有就一直输入知道-1，-1，-1
if(a==-1&&b==-1&&c==-1)break;
printf("w(%lld, %lld, %lld) = %lld\n ",a,b,c,dfs(a,b,c)) ;
}
}
int main(){
lesson1();
return 0;
}
优化后的正确答案：
#include<bits/stdc++.h>
using namespace std;
long long dp[22][22][22];
long long dfs(long long a,long long b,long long c)
{ if(a<=0||b<=0||c<=0)return 1;
if(a>20||b>20||c>20)a=b=c=20;//因为当abc大于20时都当成20使用所以不需要多次调用直接赋值
if(dp[a][b][c])return dp[a][b][c];//如果dp有值就直接反回值
if(a<b&&b<c)return dp[a][b][c]=dfs(a,b,c-1)+dfs(a,b-1,c-1)-dfs(a,b-1,c);/*dp没有值才进行计算
然后赋值个dp，然后返回*/
return dp[a][b][c]= dfs(a-1,b,c)+dfs(a-1,b-1,c)+dfs(a-1,b,c-1)-dfs(a-1,b-1,c-1);
}
void lesson1()
{
long long a,b,c;
while(cin>>a>>b>>c){//只要一直有就一直输入直到-1，-1，-1
if(a==-1&&b==-1&&c==-1)break;
printf("w(%lld, %lld, %lld) = %lld\n" ,a,b,c,dfs(a,b,c)) ;
}
}
int main(){
lesson1();
return 0;
}
P1928 外星密码
AC[3FUN]
输出：
ACFUNFUNFUN
理解题目： 可以看成一个字符串由多个字符串拼接成 S：AC(s1)DXabc(s3) （起始条件）f(s)=f(s1+s2+s3)=f(s1)+f(s2)+f(s3)//f(s2):表示D个f(x)拼接成 如果Si没有"[""]"f(Si）=si//没有加密的解密还是他本身，（终止条件）
#include<bits/stdc++.h>
using namespace std;
string f(string s)
{ string ans;
//对s中的每个字符进行遍历
for(int i=0;i<s.length();i++)
{//如果找到的字符未加密，则添加到ans中
if(s[i]!='['){
ans+=s[i];
continue;
}
//如果找到的字符串加密了，抽D和x(x的位置是j-mark的长度)
int mark=i+1,d=0,right=1;//mark会作为指针去寻找,right表示的中括号的个数
while(s[mark]>='0'&&s[mark]<='9'){//a[mark]如果是大于字符的'0'，小于字符的'9',字符串变数字
d=d*10+s[mark]-'0';//就是找到D，a[mark]-'0':就是把字符串转换成数字
mark++;//一直找数字
}
for(int j=i+1; ;j++)
{//找中括号的个数，如果[,等于]的个数那么就代表找完压缩的数据了
if(s[j]=='[')right++;
if(s[j]==']')right--;
if(right==0){
string x=s.substr(mark,j-mark);
x=f(x);
//将D个X添加到ans中
for(int k=1;k<=d;k++)ans+=x;//把很多个x拼接到ans上
i=j;
break;
}
}
//重复上面过程，返回ans的值
}
return ans;
}
int main(){
string s;
cin>>s;
cout<<f(s);
return 0;
}
P2437 蜜蜂路线
数学化抽象：f(n-m+1)
要用到高精度加法，和爬楼梯那题类似 代码
#include<bits/stdc++.h>
using namespace std;
int n,m,a[5005]={1},b[5005]={1},c[5005]={1},len=1;
void f(){
int jw=0;
for(int i=0;i<len;i++)
{
c[i]=a[i]+b[i]+jw;
jw=c[i]/10;
c[i]=c[i]%10;
}
if(jw!=0){
c[len]=jw;//进位
len++;
}
for(int i=0;i<len;i++){
a[i]=b[i];
b[i]=c[i];
}
}
int main(){
cin>>m>>n;
for(int i=3;i<=n-m+1;i++){f();}
for(int i=len-1;i>=0;i--){
cout<<c[i];
}
return 0;
}
P1164 小A点菜
4 4
1 1 2 2
输出：
3
90分代码有超时（dfs）：
#include<bits/stdc++.h>
using namespace std;
int n,m,a[105],mark[105]={0},ans=0;
void dfs(int step,int flag){//step步长，flag标记
if(step>m)return;//边界条件
if(step==m){//终止条件
ans++;
return;
}
for(int i=flag;i<n;i++){
if(mark[i]==0){
mark[i]=1;
dfs(step+a[i],i);
mark[i]=0;
}
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++)cin>>a[i];
dfs(0,0);
cout<<ans;
return 0;
}
代码（dfs）；
#include<bits/stdc++.h>
using namespace std;
int n,m,a[105],dp[101][10001];//dp记忆化
int dfs(int pos,int s){
int ans=0;
if(s==m)return 1;
else if(s>m)return 0;
if(dp[pos][s])return dp[pos][s];
for(int i=pos;i<n;i++)
ans+=dfs(i+1,s+a[i]);
return dp[pos][s]=ans;
}
void lesson1(){
cin>>n>>m;
for(int i=0;i<n;i++)cin>>a[i];
cout<<dfs(0,0);
}
int main(){
lesson1();
return 0;
}
用背包动态规划：
P1990 覆盖墙壁
#include<bits/stdc++.h>
using namespace std;
int n,f[1000005]={0,1,2},k[1000005]={0,0,1};
int main(){
cin>>n;
for(int i=3;i<=n;i++){
f[i]=(f[i-1]+f[i-2]+k[i-1]*2)%10000;
k[i]=(f[i-2]+k[i-1])%10000;
}
cout<<f[n];
return 0;
}
P3612 [USACO17JAN] Secret Cow Code S
#include<bits/stdc++.h>
using namespace std;
//找到能覆盖N的最小拓展
//将拓展进行压缩/
//压缩思路：需要将N压缩到当前拓展的前半部分
//循环上面三部操作
//知道N在初始字符串长度中，输出结果
int main(){
string s;
long long len1,len2,n,k;//len1 ：s的长度，len2最长映射长度，要多长才能包裹n
cin>>s>>n;
len1=s.length();
len2=len1;
while(len2<n)len2*=2;//找到能包裹住n的最小拓展
while(n>len1){//当n大于len1时就压缩
k=len2/2+1;
if(n>=k){//如果n的位置在拓展的右边（len2/2的右边）就要做映射，映射到拓展的左边
if(n==k)n--;
else n=n-k;
}
len2/=2;//拓展后的压缩，没用的进行压缩掉
}
cout<<s[n-1]<<endl;//因为s数组是从0开始的，n的计数是从1开始的所一要对齐
return 0;
}
P1259 黑白棋子的移动
7
输出
ooooooo*******--
oooooo--******o*
oooooo******--o*
ooooo--*****o*o*
ooooo*****--o*o*
oooo--****o*o*o*
oooo****--o*o*o*
ooo--***o*o*o*o*
ooo*o**--*o*o*o*
o--*o**oo*o*o*o*
o*o*o*--o*o*o*o*
--o*o*o*o*o*o*o*
#include<bits/stdc++.h>
using namespace std;
int n;
char a[205];
string b[4]={"ooo*o**--","o--*o**oo","o*o*o*--o","--o*o*o*o"};//特判
//输出函数
void shuchu(int l,int r){
for(int i=l;i<=r;i++)cout<<a[i];
cout<<endl;
}
void f(int step){
if(step==3){
for(int i=0;i<4;i++)
{
cout<<b[i];
shuchu(10,2*n+2);//从第10位开始到2*n+2位都进行输出
}
return;
}
shuchu(1,2*n+2);//先进行一波无脑输出 ，步长为3的时候就直接输出上面的条件里面的代码
swap(a[step],a[step*2+1]);
swap(a[step+1],a[step*2+2]);
shuchu(1,2*n+2);
swap(a[step],a[step*2-1]);
swap(a[step+1],a[step*2]);
f(step-1);//不停的往后递推
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){//初始化
a[i]='o';
a[i+n]='*';
}
a[2*n+1]='-';//初始化
a[2*n+2]='-';//初始化
f(n);//递推函数
return 0;
}
P1010 [NOIP1998 普及组] 幂次方
#include<bits/stdc++.h>
using namespace std;
int mark[20]={1};
void f(int n){//拆分
int flag=0;
while(n>=mark[flag]){
flag++;
}
flag--;
if(flag==1){
cout<<2;
}else{
if(flag==0){
cout<<"2(0)";
}else{
cout<<"2(";
f(flag);
cout<<")";
}
}
n-=mark[flag];
if(n!=0){
cout<<"+";
f(n);
}
}
int main(){
int n;
cin>>n;
for(int i=1;i<17;i++)mark[i]=mark[i-1]*2;
f(n);
return 0;
}
P1228 地毯填补问题
3
3 3
输出
5 5 1
2 2 4
1 1 4
1 4 3
4 1 2
4 4 1
2 7 3
1 5 4
1 8 3
3 6 3
4 8 1
7 2 2
5 1 4
6 3 2
8 1 2
8 4 1
7 7 1
6 6 1
5 8 3
8 5 2
8 8 1
#include<bits/stdc++.h>
using namespace std;
void f(int x,int y,int gx,int gy,int l){
if(l==1)return ;//终止条件
//先确定障碍物在那个区块
//在这个区块对应角放上一个地毯
//再将原来的大快的区块分成4个小弟区块递归即可
if(gx<=x+l/2-1&&gy<=y+l/2-1){//判断公主在左上角的区块
cout<<x+l/2<<" "<<y+l/2<<" "<<1<<endl;//在这个区块对应角放上一个地毯
f(x,y,gx,gy,l/2);//把一个长度为l的问题拆分成l/2的问题
f(x,y+1/2,x+l/2-1,y+l/2,l/2);
f(x+l/2,y,x+l/2,y+l/2-1,l/2);
f(x+l/2,y+l/2,x+l/2,y+l/2,l/2);
} else if(gx<=x+l/2-1 &&gy>=y+l/2){//障碍物在右上角
cout<<x+l/2<<" "<<y+l/2-1<<" "<<2<<endl;//在这个区块对应角放上一个地毯
f(x,y,x+l/2-1,y+l/2-1,l/2);//把一个长度为l的问题拆分成l/2的问题
f(x,y+l/2,gx,gy,l/2);
f(x+l/2,y,x+l/2,y+l/2-1,l/2);
f(x+l/2,y+l/2,x+l/2,y+l/2,l/2);
}else if(gx>=x+l/2 &&gy<=y+l/2-1){//障碍物在左下角
cout<<x+l/2-1<<" "<<y+l/2<<" "<<3<<endl;//在这个区块对应角放上一个地毯
f(x,y,x+l/2-1,y+l/2-1,l/2);//把一个长度为l的问题拆分成l/2的问题
f(x,y+l/2,x+l/2-1,y+l/2,l/2);
f(x+l/2,y,gx,gy,l/2);
f(x+l/2,y+l/2,x+l/2,y+l/2,l/2);
}else if(gx>=x+l/2 &&gy>=y+l/2){//障碍物在右下角
cout<<x+l/2-1<<" "<<y+l/2-1<<" "<<4<<endl;//在这个区块对应角放上一个地毯
f(x,y,x+l/2-1,y+l/2-1,l/2);//把一个长度为l的问题拆分成l/2的问题
f(x,y+l/2,x+l/2-1,y+l/2,l/2);
f(x+l/2,y,x+l/2,y+l/2-1,l/2);
f(x+l/2,y+l/2,gx,gy,l/2);
}
}
int main(){
int k,x,y;
cin>>k>>x>>y;
f(1,1,x,y,pow(2,k));//1,1是做上角的坐标，长度是2的k吃方 ,x,y是公主（障碍物体）
return 0;
}
P1498 南蛮图腾
#include<bits/stdc++.h>
using namespace std;
char c[2050][2050];//矩阵的大小
void f(int x,int y,int n){
if (n==1){
c[x][y+1]='/';
c[x+1][y]='/';
c[x][y+2]='\\';
c[x+1][y+3]='\\';
c[x+1][y+1]='_';
c[x+1][y+2]='_';
return;
}
int distance=pow(2,n);//pow(2,n)=2^n
f(x,y+distance/2,n-1);//一号三角形
f(x+distance/2,y,n-1);//二号三角形
f(x+distance/2,y+distance,n-1); //三号三角形
}
int main(){
int n;
cin>>n;
memset(c,' ',sizeof(c));//把所有的地方都设置成空格
f(0,0,n);
int distance=pow(2,n);
for(int i=0;i<distance;i++)//行
{
for(int j=0;j<distance*2;j++)//列
{
cout<<c[i][j];
}
cout<<endl;
}
return 0;
}
