递推

Acwing 95. 费解的开关

题目

思路

这题的大概思路有两个：dfs和递推。 如果使用dfs来做的话，可能会超时。
下面我们看看递推的大致思路：
首先我们这道题的目的是让每个灯都变亮，我们会发现其实每个灯之间都是有关系的，如果有一个灯不亮，那么他周围的灯就需要改变状态来让他变亮，但如果就这样思考的话，肯定不行，我们可以先把第一行固定下来，利用第一行的状态来递推下面几行的状态情况：首先第一行有5个灯，一共会有2^5也就是32种不同的状态，然后利用第二行和第一行的关系，去让第一行的灯全部变亮，这时第一行全部变亮了，之后再利用第三行与第二行的关系，让第二行全部变亮，以此类推，直到最后一行之前，我们都可以利用后一行与前一行的关系，让前一行变亮，但是最后一行已经没有后一行了，所有最后一行成为了判断是否全亮的标准，如果此时最后一行也是全部都亮的，那么就说明此时枚举的这种状态可以成功，但不一定是最简的，所有程序中要维护一个最小变量。

注意点

这里面有一个困扰我很久的地方：为什么是k>>i&1的时候进入if，不应该是灯不亮的时候进去if，然后利用turn函数让它变量吗？其实并不是这样的，这说明我对k还没有理解，k是用来枚举第一行的32种不同状态的，例如：如果k=0，换成5位的二进制也就是00000,这里的0表示状态不需要发生变化，如果k=1，二进制也就是00001，表示最后一个位置要发生变化。

代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=6;
char p[N][N],temp[N][N];
int dx[5]={-1,1,0,0,0},dy[5]={0,0,-1,1,0};void turn(int a,int b)
{for(int i=0;i<5;i++){int na=a+dx[i],nb=b+dy[i];if(na<0||na>=5||nb<0||nb>=5) continue;else{p[na][nb]^=1; // 因为‘0’的阿斯克码为48，而1为49，只有一位不同，所有可以这么做。}}
}int main()
{int t=0;cin>>t;while(t--){for(int i=0;i<5;i++){cin>>p[i];}int res=10;for(int k=0;k<32;k++){int step=0;  //注意这个step要写在循环里面，因为针对每种情况step都要重新计算，以求出最小值。memcpy(temp,p,sizeof p);for(int i=0;i<5;i++)   //枚举第0行的32种不同的状态{if(k>>i&1)   //这里的k代表32种不同的状态，1表示与原来的状态不同，0表示与原来的状态相同{step++;turn(0,i);}}for(int i=0;i<4;i++){for(int j=0;j<5;j++){if(p[i][j]=='0'){step++;turn(i+1,j); //只能由它的下一行元素来改变它，这是由它所具有的性质决定的。}}}bool dark=false;  //用来判断最后一行是否有没有亮的灯，如果没有，则说明可以成功。for(int j=0;j<5;j++){if(p[4][j]=='0'){dark=true;}}if(!dark){res=min(res,step);}memcpy(p,temp,sizeof temp);  //拷贝两次，是为了你枚举下一种情况时，p还是原来输入的状态。}if(res>6) cout<<-1<<endl;else cout<<res<<endl;}return 0;
}

Acwing717.简单斐波那契

题目

最多的写法（递归）

#include<iostream>
using namespace std;
//递归的写法 将大问题分解成小问题
const int N=50;
int f[N];
int n;int  fei(int n)
{if(n==1){return 0;}if(n==2){return 1;}else{return fei(n-1)+fei(n-2);}
}int main()
{cin>>n;f[1]=0,f[2]=1;for(int i=1;i<=n;i++){printf("%d ",fei(i));}return 0;
}

不过一般使用递归来写这种题目肯定会超时的，这题也是同样。

递推

递归的本质：其实就是将大问题化成小问题，但在这题中，有些fn被求了许多次，也就造成了没有必要的重复，而且递归时，会调用递归栈，同样也需要花费很多的时间，其实我们不妨反过来想：我们不妨先求出来小问题，然后由小问题来求一个大问题。

//递推的写法，与递归正好相反，它是由小问题组成大问题。
int main()
{int n=0;cin>>n;int f[50]={0};f[1]=0,f[2]=1;for(int i=3;i<=n;i++){f[i]=f[i-1]+f[i-2];}for(int i=1;i<=n;i++){printf("%d ",f[i]);}return 0;
}

优化

上面的递推写法其实已经可以过了，我们发现求这个fn时其实只是循环用到了两个变量f(i-1),f(i-2)。根本没有必要开一个数组出来。

//滚动数组的写法
int main()
{int n=0;cin>>n;int a=0,b=1; //这儿的a，b就相当于之前写法的f(i-2)和f(i-2)for(int i=1;i<=n;i++){cout<<a<<" ";int fn=a+b;a=b,b=fn;}return 0;
}

递归

递归其实包含很多，很多地方都会用来，所以这儿也没有给出一个定义，总之就是：大问题化成小问题。

Acwing92. 递归实现指数型枚举

解法：dfs（属于递归的一种）

做dfs时一定要注重顺序，以一种什么样的顺序来实现目的。
下面是两种最常用的顺序，其中第二种依次枚举每个位置放哪个数，这种顺序最为常用。

y总遍历的顺序

y总这种遍历的顺序其实以上两种都不属于，他的顺序是看每个位置的这个数要不要选择。

#include<iostream>
using namespace std;const int N=20;
int n;
bool st[N];void dfs(int u)
{if(u>n){for(int i=1;i<=n;i++){if(st[i]){printf("%d ",i);}}printf("\n");return;}st[u]=true;dfs(u+1);st[u]=false;dfs(u+1);
}int main()
{cin>>n;dfs(1);return 0;
}

递归图解分析

代码随想录的遍历顺序

他的这种遍历顺序就是刚刚说的那个第二种遍历顺序：每个位置应该放哪个数。

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己if (startIndex >= nums.size()) { // 终止条件可以不加return;}for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};

Acwing94. 递归实现排列型枚举

解法：dfs（其实和上一题差不多）

这题其实和上一题差不多，不过不需要从哪个数开始而已。

这一题y总和代码随想录都是用的第二种遍历顺序：每个位置应该放哪个数。

y总的写法：

#include<iostream>
using namespace std;const int N=20;
int n;
int state[N];
bool st[N];void dfs(int u)  //u其实是代表第几个位置
{if(u>n)    //这儿不能写成u==3，因为最后出去的时候u是等于4的{for(int i=1;i<=n;i++){printf("%d ",state[i]);}printf("\n");return ;}for(int i=1;i<=n;i++){if(!st[i]){st[i]=true;state[u]=i;dfs(u+1);state[u]=0;  //恢复现场用的st[i]=false;}}
}int main()
{cin>>n;dfs(1);return 0;
}

代码随想录的写法（其实差不多，只不过题目可能提供的参数不一样）

class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking (vector<int>& nums, vector<bool>& used) {// 此时说明找到了一组if (path.size() == nums.size()) {result.push_back(path);return;}for (int i = 0; i < nums.size(); i++) {if (used[i] == true) continue; // path里已经收录的元素，直接跳过used[i] = true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] = false;}}vector<vector<int>> permute(vector<int>& nums) {result.clear();path.clear();vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}
};