第一讲 递归与递推

准备：做题的套路

做题步骤

  1. 根据题目描述，抽象出模型
  2. 不断思考尝试，能不能用dfs？图论？dp？贪心？
  3. 检查
    1. 正确性
    2. 时间复杂度

注意：多用草稿纸，多模拟，少空想。

C++，一秒钟大概能执行1亿次，10^8次，如果时间复杂度小于此值，那么就能在1秒钟之内算出来。

给出不同数据范围下，代码的时间复杂度和算法该如何选择。

一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 107∼108107∼108 为最佳。 下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择： 1递归与递推 - 图1

例如：如果数据范围比较小（n<30），那么时间复杂度要求比较低，为指数级别，可以使用dfs+减枝算法。

如果n<=100，O(n^3)

如果n<=1000，O(n^2)

这样可以做一个粗略的判断，这道题可能是什么时间复杂度，应该用什么算法。

第一节 递归

scanf、printf和cin、cout的使用区别

1递归与递推 - 图2

引子：斐波那契数列

1递归与递推 - 图3

递归搜索树，帮助理解递归

1递归与递推 - 图4

例题：递归实现指数型枚举

https://www.acwing.com/problem/content/94/

题目描述
从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。 输入格式
输入一个整数n。 输出格式
每行输出一种方案。 同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。 对于没有选任何数的方案，输出空行。 本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。 数据范围
1≤n≤15 输入样例：
3
输出样例： 3
2
2 3
1
1 3
1 2
1 2 3

思路：

指数型枚举，给他n个坑，然后就是每个坑选与不选的问题。

1递归与递推 - 图5

代码：

一般先无脑打上这四个头文件

1递归与递推 - 图6

mycode：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  7. const int N = 16;   //use index 1-15
  8. int st[N];          //状态：记录每个位置的状态：0表示还没考虑，1表示选它，2表示不选它。
  9. int n;              //1-n个数
  11. void dfs(int c) {
  12.     if(c > n) {
  13.         //输出方案
  14.         for(int i = 1; i <= n; i++) {
  15.             if(st[i] == 1){
  16.                 cout << i << " ";
  17.             }
  18.         }
  19.         cout << "\n";
  20.         return;
  21.     }
  22.     //不选它
  23.     st[c] = 2;
  24.     dfs(c + 1);
  25.     st[c] = 0;
  26.     //选它
  27.     st[c] = 1;
  28.     dfs(c + 1);
  29.     st[c] = 0;
  30. }
  32. int main() {
  33.     cin >> n;
  34.     dfs(1);
  35.     return 0;
  36. }

例题：递归实现排列型枚举

https://www.acwing.com/problem/content/96/

题目描述
把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。 输入格式
一个整数n。 输出格式
按照从小到大的顺序输出所有方案，每行1个。 首先，同一行相邻两个数用一个空格隔开。 其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。 数据范围
1≤n≤9 输入样例
3
输出样例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

字典序概念：比较简单，不多说。

ai不存在则认为它是最小的，所以一定小于存在的bi。

想一个递归枚举全排列，就要先想一个顺序。一般有两种方式。

  1. 依次枚举每个数，放到哪个位置。
  2. 依次枚举每个位置放哪个数。

该题的递归搜索树。

1递归与递推 - 图7

这个就是枚举每个坑应该放什么数。

观察这个递归搜索树，已经按照字典序排列了。

想一下我们枚举的次序，都是从小到大枚举，能够直接按照字典序排列也就不足为奇了。

my code

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  7. const int maxn = 10; //use index 1-9
  8. int n;
  9. int st[maxn];  //状态，0表示没放，1~n表示放了的数
  10. bool used[maxn];   //false表示没有用，true表示用了
  12. void dfs(int step) {
  13.     //数填满了
  14.     if(step > n) {
  15.         //输出方案
  16.         for(int i = 1; i <= n; i++ ) {
  17.             cout << st[i] << " ";
  18.         }
  19.         cout << "\n";
  20.     }
  21.     //枚举当前位置能够填的数
  22.     for(int i = 1; i <= n; i++ ) {
  23.         if(!used[i]){
  24.             st[step] = i;
  25.             used[i] = true;
  26.             dfs(step + 1);
  27.             used[i] = false;
  28.         }
  29.     }
  30. }
  32. int main() {
  33.     cin >> n;
  34.     dfs(1);
  36.     return 0;
  37. }

时间复杂度的思考，暂不关注，反正是指数级别。

作业：递归实现组合型枚举

https://www.acwing.com/problem/content/95/

题目描述
从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。 输入格式
两个整数 n,m ,在同一行用空格隔开。 输出格式
按照从小到大的顺序输出所有方案，每行1个。 首先，同一行内的数升序排列，相邻两个数用一个空格隔开。 其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 5 7排在1 3 6 8前面）。 数据范围
n>0,
0≤m≤n ,
n+(n−m)≤25 输入样例：
5 3
输出样例：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

思路：

组合型枚举，也就是排列组合中的组合，排列需要输出每种顺序，组合则每种顺序都算一种。

此题要求按字典序输出组合，那组合中的后一个数总是比前一个数大，由此特性，添加了一个变量start，使得循环总从start开始执行。

my code way：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  7. const int maxn = 51;
  8. int a[maxn];
  10. int n,m;
  12. void dfs(int step, int start) {
  13.     //如果位数满了，那么输出 
  14.     if(step > m){
  15.         for(int i = 1; i <= m; i++) {
  16.             cout << a[i] << " ";
  17.         }
  18.         cout << "\n";
  19.         return;
  20.     }
  21.     for(int i = start; i <= n; i++) {
  22.         a[step] = i;
  23.         dfs(step + 1, i + 1);
  24.         //a[step] = 0;//恢复现场,这里可以省略 
  25.     }
  26. }
  28. int main() {
  29.     cin >> n >> m;
  30.     dfs(1,1);
  31.     return 0;
  32. }

my code 剪枝优化：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  7. const int maxn = 51;
  8. int a[maxn];
  10. int n,m;
  12. void dfs(int step, int start) {
  13.     //剪枝：如果已经选了的位数+能选的剩余位数仍然小于m，那么直接返回 
  14.     if(step-1 + (n-start+1) < m) return;
  15.     //如果位数满了，那么输出 
  16.     if(step > m){
  17.         for(int i = 1; i <= m; i++) {
  18.             cout << a[i] << " ";
  19.         }
  20.         cout << "\n";
  21.         return;
  22.     }
  23.     for(int i = start; i <= n; i++) {
  24.         a[step] = i;
  25.         dfs(step + 1, i + 1);
  26.         //a[step] = 0;//恢复现场,这里可以省略 
  27.     }
  28. }
  30. int main() {
  31.     cin >> n >> m;
  32.     dfs(1,1);
  33.     return 0;
  34. }

作业：带分数

https://www.acwing.com/problem/content/1211/

100 可以表示为带分数的形式：100=3 + 69258 / 714
还可以表示为：100=82 + 3546 / 197
注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。 类似这样的带分数，100 有 11 种表示法。 输入格式
一个正整数。 输出格式
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。 数据范围
1≤N<106 样例
输入样例1：
100
输出样例1：
11
输入样例2：
105
输出样例2：
6

代码：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  7. const int maxn = 100;
  8. int st[10];//保存全排列的结果 
  9. bool book[10];//标记使用过,用1-9 
  11. int calc(int l,int r) {
  12.     int res = 0;
  13.     for(int i = l; i <= r; i++) {
  14.         res = res * 10 + st[i];
  15.     }
  16.     return res;
  17. }
  19. int dfs(int step, int target, int& ans) {
  20.     if(step > 9){
  21.         //两层循环分三段 
  22.         for(int i = 1; i <= 7; i++) {
  23.             for(int j = i + 1; j <= 8; j++) {
  24.                 int b = calc(i+1, j);
  25.                 int c = calc(j+1, 9);
  26.                 if(b%c != 0)continue; 
  27.                 int a = calc(1, i);
  28.                 if(a + (b/c) == target)
  29.                     ans++;
  30.             }
  31.         }
  32.     }
  33.     for(int i = 1; i <= 9; i++) {
  34.         if(book[i] == false){
  35.             st[step] = i;
  36.             book[i] = true;
  37.             dfs(step + 1, target, ans);
  38.             book[i] = false;
  39.         }
  40.     }
  41. }
  43. int main() {
  44.     int n, ans;
  45.     cin >> n;
  46.     ans = 0;
  47.     dfs(1,n,ans);
  48.     cout << ans;
  49.     return 0;
  50. }

优化算法：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  6. using namespace std;
  8. const int N = 10;
  10. int n;
  11. bool st[N], backup[N];
  12. int ans;
  14. bool check(int a, int c)
  15. {
  16.     int b = n * c - a * c;
  18.     if (!a || !b || !c) return false;
  20.     memcpy(backup, st, sizeof st);
  21.     while (b)
  22.     {
  23.         //逐个取数
  24.         int x = b % 10;
  25.         b /= 10;
  26.         if (!x || backup[x]) return false;//如果该位是0或该位数字用过了，返回false； 
  27.         backup[x] = true;//标记用过 
  28.     }
  29.     //如果1-9都用过了，那么正确 
  30.     for (int i = 1; i <= 9; i ++ )
  31.         if (!backup[i])
  32.             return false;
  34.     return true;
  35. }
  37. void dfs_c(int a, int c)
  38. {
  39.     if (check(a, c)) ans ++ ;
  41.     for (int i = 1; i <= 9; i ++ )
  42.         if (!st[i])
  43.         {
  44.             st[i] = true;
  45.             dfs_c(a, c * 10 + i);
  46.             st[i] = false;
  47.         }
  48. }
  50. void dfs_a(int a)
  51. {
  52.     if (a >= n) return;
  53.     if (a) dfs_c(a, 0);
  55.     for (int i = 1; i <= 9; i ++ )
  56.         if (!st[i])
  57.         {
  58.             st[i] = true;
  59.             dfs_a(a * 10 + i);
  60.             st[i] = false;
  61.         }
  62. }
  64. int main()
  65. {
  66.     cin >> n;
  67.     dfs_a(0);
  68.     cout << ans << endl;
  69.     return 0;
  70. }

比赛中使用第一种方法即可。在比赛中，需要使用更加稳妥的算法来AC。

第二节 递推

例题：斐波那契数列

https://www.acwing.com/problem/content/719/

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

输入格式

一个整数N。

输出格式

在一行中输出斐波那契数列的前N项，数字之间用空格隔开。

数据范围

0

输入样例：

5

输出样例：

0 1 1 2 3

way 1 code：

  1. #include <iostream>
  2. using namespace std;
  4. const int maxn = 50;
  5. long long arr[maxn]={0,1};
  7. int main(){
  8.     int n;
  9.     cin >> n;
  10.     for(int i = 0; i < n; i++) {
  11.         if(i >= 2) arr[i] = arr[i-1] + arr[i-2];
  12.         cout << arr[i] << " ";
  13.     }
  14.     return 0;
  15. }

way 2 code:

  1. #include <iostream>
  2. using namespace std;
  4. const int maxn = 50;
  6. int main(){
  7.     int n;
  8.     cin >> n;
  10.     int a,b,c;
  11.     a = 0; b = 1;
  12.     for(int i = 0; i < n; i++) {
  13.         cout << a << " ";
  14.         c = a + b;
  15.         a = b;
  16.         b = c;
  17.     }
  18.     return 0;
  19. }

way2有滚动数组的思想。

例题：费解的开关

https://www.acwing.com/problem/content/97/

你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。 我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态 10111
01101
10111
10000
11011 在改变了最左上角的灯的状态后将变成： 01111
11101
10111
10000
11011 再改变它正中间的灯后状态将变成： 01111
11001
11001
10100
11011 给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。

输入格式

第一行输入正整数n，代表数据中共有n个待解决的游戏初始状态。 以下若干行数据分为nn组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。

输出格式

一共输出nn行数据，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。 对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出“-1”。

数据范围

0

输入样例：

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

思路：

枚举第一行的所有按法，按下第一行，然后根据第一行的情况，按第二行，使得第一行为全亮，之后根据第二行的情况，按第三行，使得第二行全亮，以此类推。最后，如果按照这种按法，最后一行全亮了，那么这是一种解，比较最小步数。最后得到答案。

mycode：

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  7. int a[5][5];//存灯表 
  8. int backup[5][5];//备份，用于回溯
  10. int xg[5][2] = {
  11.     {0,0},{0,1},{0,-1},{1,0},{-1,0},
  12. };//5个相关灯的偏移量 
  14. int cstep,mstep = 9999;
  16. //对应坐标取反 
  17. void qf(int x, int y) {
  18.     a[x][y] = (a[x][y]==0 ? 1 : 0);
  19. }
  21. //改变第x行第y列灯和相关灯的状态 
  22. void turn(int x, int y) {
  23.     for (int i = 0; i < 5; i++) {
  24.         int tx = x + xg[i][0];
  25.         int ty = y + xg[i][1];
  26.         if(tx < 0 || tx > 4 || ty <0 || ty > 4)continue;
  27.         qf(tx,ty);
  28.     }
  29. }
  31. void solve() {
  32.     memcpy(backup, a, sizeof a);//将a备份
  33.     mstep = 9999;//重置最小步
  34.     //枚举第一行的所有按法，从二进制00000 ~ 11111，1表示要按，0表示不按
  35.     for (int op = 0; op <= 31; op++) {
  36.         //尝试这一种按法 
  37.         cstep = 0;//当前步数重置为0
  38.         for (int i = 0; i < 5; i++) {
  39.             if((op >> i) & 1) {
  40.                 turn(0, 4-i);
  41.                 cstep ++;
  42.             }
  43.         }
  44.         //根据第i行来按第i+1行
  45.         for (int i = 0; i < 4; i++) {
  46.             for (int j = 0; j < 5; j++) {
  47.                 if(a[i][j] == 0) {
  48.                     turn(i + 1, j);
  49.                     cstep ++;
  50.                 }
  51.             }
  52.         }
  53.         //如果最后第4行为全1，那么方案成功，更新最小步数 
  54.         int j;
  55.         for (j = 0; j < 5; j++) {
  56.             if(a[4][j] == 0)break;
  57.         }
  58.         if(j == 5) {//没有提前跳出，所以最后一行全为1 
  59.             mstep = min(cstep,mstep);//更新最小步数 
  60.         }
  61.         //该次尝试结束，回溯恢复a
  62.         memcpy(a, backup, sizeof backup);
  63.     }
  64. }
  66. int main() {
  67.     //一个一个出解 
  68.     int n;
  69.     cin >> n;
  70.     for (int i = 0; i < n; i++) {
  71.         for (int j = 0; j < 5; j++) {
  72.             for (int k = 0; k < 5; k++) {
  73.                 scanf("%1d", &a[j][k]);
  74.             }
  75.         }
  76.         //输完一个开始处理 
  77.         solve();
  78.         //如果步数超或无解(mstep==9999)，则输出-1 
  79.         if(mstep > 6) mstep = -1;
  80.         cout << mstep << endl;
  81.     }
  82.     return 0;
  83. }

作业：飞行员兄弟

https://www.acwing.com/problem/content/118/

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有16个把手的冰箱。 已知每个把手可以处于以下两种状态之一：打开或关闭。 只有当所有把手都打开时，冰箱才会打开。 把手可以表示为一个4х4的矩阵，您可以改变任何一个位置[i,j]上把手的状态。 但是，这也会使得第i行和第j列上的所有把手的状态也随着改变。 请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式

输入一共包含四行，每行包含四个把手的初始状态。 符号“+”表示把手处于闭合状态，而符号“-”表示把手处于打开状态。 至少一个手柄的初始状态是关闭的。

输出格式

第一行输出一个整数N，表示所需的最小切换把手次数。 接下来N行描述切换顺序，每行输入两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。 注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

数据范围

1≤i,j≤4

输入样例：

  1. -+--
  2. ----
  3. ----
  4. -+--

输出样例：

6
1 1
1 3
1 4
4 1
4 3
4 4

思路：

枚举所有按法，使得把手全开，比较最小步数，同时记录最小步数的操作。

mycode：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

char a[4][5],backup[4][5];
int mop;
int cstep,mstep = 9999;

void qf(int x, int y) {
    a[x][y] = (a[x][y] == '-' ? '+' : '-'); 
}

void turn(int x, int y) {
    for (int i = 0; i < 4; i++) {
        qf(i, y);
        qf(x, i);
    }
    qf(x, y);
}

void solve() {
    //枚举所有操作0~2^16-1
    memcpy(backup, a, sizeof a);//备份 
    for (int op = 0; op < 65536; op++) {
        //执行当前操作
        cstep = 0; // 重置当前步 
        for (int i = 0; i < 16; i++) {
            if (op >> i & 1) {
                turn(i / 4, i % 4);
                cstep ++;
            }
        }
        //如果全是-，那么成功，判最小步
        int i;
        for (i = 0; i < 16; i++) {
            if (a[i/4][i%4] == '+') break;
        }
        if(i == 16) {//全是-,判最小步 
            if(cstep < mstep) {
                mstep = cstep;
                mop = op;//记录最小步的操作 
            }
        }
        //回溯恢复 
        memcpy(a, backup, sizeof backup);
    }
}

int main() {
    for (int i = 0; i < 4; i++) {
        cin >> a[i];//评测系统用不了gets是没想到的 
    }
    solve();
    //输出最小步 
    cout << mstep << endl;
    //输出最小步的操作
    for(int i = 0; i < 16; i++) {
        if(mop >> i & 1) {
            cout << i / 4 + 1 << " ";
            cout << i % 4 + 1 << "\n";
        }
    }
    return 0;
}

作业：翻硬币

https://www.acwing.com/problem/content/1210/

小明正在玩一个“翻硬币”的游戏。 桌上放着排成一排的若干硬币。我们用 表示正面，用 o 表示反面（是小写字母，不是零）。 比如，可能情形是：`oooooo如果同时翻转左边的两个硬币，则变为：oooo*oooo` 现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？ 我们约定：把翻动相邻的两个硬币叫做一步操作。

输入格式

两行等长的字符串，分别表示初始状态和要达到的目标状态。

输出格式

一个整数，表示最小操作步数

数据范围

输入字符串的长度均不超过100。
数据保证答案一定有解。

输入样例1：

**********
o****o****

输出样例1：

5

输入样例2：

*o**o***o***
*o***o**o***

输出样例2：

1

思路：递推方法，设初始状态为a，目标状态为b，如果ai ≠ bi，则翻转ai 和 ai+1，inc步数，因为题目说明一定有解，所以一定能翻转成功，最后得到结果。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

char a[110],b[110];

void qf(int i) {
    a[i] = (a[i] == '*'?'o':'*');
}

int main() {
    cin >> a >> b;//空格和换行都会进下个输入
    int res = 0;
    int len = strlen(a);
    for (int i = 0; i < len - 1; i++) {
        if (a[i] != b[i]) {
            qf(i);
            qf(i+1);
            res++;
        }
    }
    cout << res;
    return 0;
}