递推

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;
    }
};