【算法经典题集】递推(持续更新~~~)

😽PREFACE
🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝
📢系列专栏：算法经典题集
🔊本专栏涉及到的知识点或者题目是算法专栏的补充与应用
💪种一棵树最好是十年前其次是现在

递推

简单的斐波那契

题目
以下数列 0 1 1 2 3 5 8 13 21 ... 被称为斐波纳契数列。
这个数列从第 33 项开始，每一项都等于前两项之和。
输入一个整数 N，请你输出这个序列的前 N 项。

输入格式
一个整数 N
输出格式
在一行中输出斐波那契数列的前 NN 项，数字之间用空格隔开。
数据范围
0<N<46

输入样例：
5
输出样例：
0 1 1 2 3

参考代码

//滚动数组
#include <bits/stdc++.h>
using namespace std;
int n;
int a,b=1,c;
int main()
{cin>>n;while(n--)//进行n次，然后结束，等价于for(int i = 0; i < n; i ++){cout<<a<<" ";// 输出第一个c=a+b;// 求出末项的值a=b;// 由于下次直接输出，所以，这里要提前滚动b=c;// 滚动}return 0;
}

费解的开关

题目：
你玩过“拉灯”游戏吗？
2525 盏灯排成一个 5×55×5 的方形。
每一个灯都有一个开关，游戏者可以改变它的状态。
每一步，游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。

下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：
01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在 66 步以内使所有的灯都变亮。

输入格式
第一行输入正整数 nn，代表数据中共有 nn 个待解决的游戏初始状态。
以下若干行数据分为 nn 组，每组数据有 55 行，每行 55 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式
一共输出 nn 行数据，每行有一个小于等于 66 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若 66 步以内无法使所有灯变亮，则输出 −1−1。
数据范围
0<n≤500

输入样例：
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
输出样例：
3
2
-1

问题1：为什么要枚举第一排32种方案 第一排灯亮暗是输入的是已知的，那就应该针对第一排的灯接着往下递归啊，但这么做答案就是固定的，也不确定是最小步，可是枚举所有方案的意义在哪啊
答：我们输入的已知的是第一行灯亮或暗的状态，而我们枚举的32种是我们对灯的操作，按还是不按。如果通过操作使得第一行灯的亮暗状态发生了改变，那么接下来我们对第二行的操作就也会随之改变，继而导致整个步数都会有变化，所以用res来留存最小的。
思路：先对第一行进行32种操作的枚举，列出所有操作后第一行可能的状态（操作算步数 step++），一旦第一行的每盏灯的亮暗情况确定了，那么该方案的步数也就确定了
补充为什么要枚举第一行的所有情况：
1，第一行确定余下四行的开灯结果是固定的是必然的发生的
2，第一行的五个开关也是可以按动的，不同的按动会有不同的结果共有2的5次方种结果

分析：枚举第一行的意义是：不需要在意第一行的灯是灭是暗，只需把第一行的按法枚举一遍，也就是我们说的 “操作”，每个位置都有两种选择，按(用1表示)或者不按(用0表示)，遍历这32种操作引发的情况，每一次再通过res = min(res, step);把最小步数存一下，就能找到最优解

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>using namespace std;const int N = 6;
int dx[N] = {-1, 0, 1, 0, 0}, dy[N] = {0, 1, 0, -1, 0};
char g[N][N], backup[N][N];// 这个操作是把(x, y)以及上下左右的灯都变成相反的颜色
void turn (int x, int y)
{for (int i = 0; i < 5; i ++ ){int a = x + dx[i], b = y + dy[i];//如果在边界外边，直接忽略即可if (a < 0 || a >= 5 || b < 0 || b >= 5) continue;g[a][b] ^= 1;   //异或，不同的时候就变成相反的数}}int main()
{int n;scanf("%d", &n);while(n -- ){// 按行输入，把每一行当成一个字符串for (int i = 0; i < 5; i ++ ) cin >> g[i];int res = 10;// 这里我们枚举了第一行的32种按法，不用管是亮是灭，把第一行所有情况都按一遍// 按每种情况的第一行，去遍历接下来的行// 枚举32种第一行的按法只是可能会减少步数，如果直接从第二行开始答案一定是固定的了，找不到最优解或者可能没有解for (int op = 0; op < 32; op ++ ){// 我在对这种情况操作的时候，得先备用一下// 把原始数组备份一下，然后操作g，操作完了还原，然后再操作memcpy(backup, g, sizeof g);int step = 0;// 第一行的按法(在这里 1 表示按了, 0 表示不按)，这里只是为了输出第一行按完之后的状态for (int i = 0; i < 5; i ++ )if (op >> i & 1)  // 数字2 对应了 00010 表示第2个位置的按一下// 00010 >> 1 & 1  是1 所以turn(0, 1) 就是第一行第二个位置{                 // 数字3 对应了00011 表示第1 和第2个位置的按一下step ++ ;turn (0, i);;}// 然后通过第一行按完之后的状态，按234行for (int i =0; i < 4; i ++ )for (int j = 0; j < 5;j ++ )if (g[i][j] == '0'){step ++;turn (i + 1, j);  // 如果这个位置是灭的，就按下一行对应的位置}bool dark = false;for (int j = 0; j < 5; j ++ )if (g[4][j] == '0'){dark = true;break;}// 对于32种情况的这一种，如果所有的全亮就记录下步数(事实上只记录了最后一行是否dark)if (!dark) res = min(res, step);memcpy (g, backup, sizeof g);}if(res > 6) res = -1;cout << res << endl;}return 0;
}

翻硬币

题目：
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：**oo***oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式
一个整数，表示最小操作步数
数据范围
输入字符串的长度均不超过100。
数据保证答案一定有解。

输入样例1：
**********
o****o****
输出样例1：
5
输入样例2：
*o**o***o***
*o***o**o***
输出样例2：
1

#include <bits/stdc++.h>
using namespace std;
const int N=110;
char s[N],e[N];void turn(int i)
{if(s[i]=='*'){s[i]='o';}else{s[i]='*';}
}int main()
{cin>>s>>e;int cnt=0;int n=strlen(s);for(int i=0;i<n-1;i++){if(s[i]!=e[i]){turn(i),turn(i+1);cnt++;}}cout<<cnt<<endl;return 0;
}