递推问题

递推：

在面对一个大任务的时候，有时候我们可以将大任务划分为小任务，再将小任务划分为更小的任务......，直到遇到初始情况，最后由初始情况一直往前推进，最后解决大任务，这就是递推的思想。

递推问题：

例题1.砖块：

由n 个砖块排成一排，从左到右编号依次为 1∼n，砖块分为黑色（B）和白色（W），每次可以改变相邻两个砖块的颜色。问需要多少次将所有砖块变成一种颜色；

如果可以，输出次数与任意一种改变方案（改变n[k]和n[k]时，输出k）;

如果不行输出-1。

思路：

首先，我们假设改变p[k]时，p[k+1]一同变换；

每块砖最多只需要改变一次；

最后需要把所有砖变成W或者B，假设全变为W；

从第一块开始，如果第一块不为W，就改变p[k]与p[k+1]，一直扫描到第n-1块砖；

如果最后的一块砖为W，则该情况有解，否则无解；

假设全变为B，重复上述操作即可。

代码如下：

string str;//字符//改变字符为对应字符
void update(char &c){c=='W'?c='B':c='W';
}//判断是否能全变为st
bool check(char st,int n){vector<int>res;//变换的位置string s=str;//注意可能判断两次，不能改变str//如果不为st,则改变for(int i=0;i<n-1;i++)if(s[i]!=st){update(s[i]);update(s[i+1]);res.push_back(i);}//如果最后一位是stif (s[n-1]==st){cout<<res.size()<<endl;if(res.size()){for(int i=0;i<res.size();i++)cout<<res[i]+1<<" ";cout<<endl;}return true;}return false;
}int main(){int n;//字符串长度cin>>n>>str;if(!check('W',n)&&!check('B',n))cout<<"-1"<<endl;//如果两种情况都不行return 0;
}

例题2.费解的开关：

25盏灯排成一个5*5的方形，每一个灯有开(1)和关(0)两种状态，每一次可以改变一盏灯的状态，并且这盏灯的上下左右相邻的灯的状态也都会改变，问最少需要几步可以让所有灯都亮。如果超过六步，则输出-1，否则输出次数。

思路:

每盏灯只有该变一次的必要；

我们先枚举第一行灯的状态（只改变第一盏灯）;

因为所有的灯都需要点亮，这时我们就根据第一行灯的状态来改变第二行灯的状态，然后根据第二行的状态.......，最后根据第四行的状态来改变第五行；

最后判断最后一行是否全亮，如果全亮则有解，反之无解；

代码如下：

const int N=6;
int g[N][N],tmp[N][N];//灯，并且把灯的状态复制一份
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};void f(int x,int y){//开关(x,y)g[x][y]==0?g[x][y]=1:g[x][y]=0;for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];if(a<0||b>=5||b<0||b>=5)continue;g[a][b]==0?g[a][b]=1:g[a][b]=0;}return;
}//要枚举很多次，每次枚举不能改变原始状态
int main(){memcpy(tmp,g,sizeof g);int res=7;for(int i=0;i<pow(2,5);i++){//二进制枚举，5个二进制位int s=0;//记录改变了几次for(int i=0;i<5;i++)//每次将g重置for(int j=0;j<5;j++)g[i][j]=tmp[i][j];for(int j=0;j<5;j++){//右移j位if(((i>>j)&1)==1){s++;f(0,j);}}for(int k=0;k<4;k++)//枚举前4行for(int u=0;u<5;u++){if(g[k][u]==0){s++;f(k+1,u);}}for(int k=0;k<5;k++)//判断最后一行是否全亮if(g[4][k]==0)s=7;if(s<=6)res=min(s,res);}return 0;}

以集合的视角看待一些递推问题：

很多递推问题让我们求的是方法数/数量、最值等问题，我们可以将要求的东西(方法数等)看作是一个集合，将此集合做一个不重不漏的划分，每个子集也可以以同样的方式划分，就可以得到递推式（子集之和、最值等）。

例题1.数楼梯：

楼梯有 N 阶，从一楼开始上楼，上楼可以一步上一阶，也可以一步上二阶。计算共有多少种不同的走法。

思路：

f[i]表示走到i位置的方法数；

f[k] = f[k-1] + f[k-2]；

将走到k阶楼梯的方法数看作是一个集合；

因为只能从k-1和k-2的位置走到k，那么我们可以把走到k的方法数这个集合划分为走到第k-1和走到第k-2这两个台阶的方法集合，这时理解f[k] = f[k-1] + f[k-2]的含义就很容易了。

例题2.过河卒：

棋盘上 A点有一个过河卒，需要走到目标 B 点；

卒行走的规则：可以向下、或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”；

现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

思路：

f[a][b]表示走到(a,b)的方法数；

f[a][b] = f[a-1][b] + f[a][b-1]；

将走到(a,b)点的方法数看做是一个集合；

由于(a,b)只能是(a-1,b)和(a,b-1)走到的，将(a,b)集合不重不漏的划分为两个集合，走到(a,b)的方法数应该是走到(a-1,b)的方法数加上走到(a,b-1)的方法数。那么f[a][b] = f[a-1][b] + d[a][b-1]。

例题3.数字三角形：

给定一个数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

思路：

g[i][j]表示三角形(i,j)位置的数，f[i][j]表示走到(i,j)点的最大值;

f[i][j] = max( f[i-1][j-1] , f[i-1][j] ) + g[i][j];

将走到(i , j)点的最大值看作是一个集合，那么这个集合可以划分为从左上角走过来和从右上角走过来这两个集合，我们将两个集合取最大值然后加上g[i][j]即可。