洛谷官方题单——递推和递归题解

递推算是我们学习数学的基本功了，而算法在某些程度上就是披着程序设计的数学。而且我们最早接触递推便是高中数列的递推式，其对我们来说不会陌生。
而对于递归，我们可以看到在进入算法tag的题解中，或多或少的有着递归的影子，这一题单就是帮助我们更好的理解递归这一在程序设计中显著减少代码量的技巧。

题目0：上楼梯

简单的递推，由于我们能到达第i层只能从第i-1层或者第i-2层到达，所以dp[i]=dp[i-1]+dp[i-2]，是不是很熟悉？就是斐波拉契数列，然后我们欢快的打上fib的代码

#include<stdio.h>
long long int memo[5050];
int main(){
    int n;
    scanf("%d",&n);
    memo[1]=1,memo[2]=2;
    for(int i=3;i<=n;i++)
        memo[i]=memo[i-1]+memo[i-2];
    return 0*printf("%d\n",memo[n]);
}

然后你就会发现，你WA了，这是为什么呢？仔细康康数据范围，再想想什么时候fib越过longlong，故我们需要使用高精度+递推（？这真的只是普及-么？）
我们加一点点细节，得到了这个代码。

#include<stdio.h>
int len = 1, dp[5050][5050];
void work(int n){
    for (int i = 1; i <= len; i++)
        dp[n][i] = dp[n - 1][i] + dp[n - 2][i];
    for (int i = 1; i <= len; i++)
        if (dp[n][i] >= 10){
            dp[n][i + 1] += dp[n][i] / 10;
            dp[n][i] = dp[n][i] % 10;
            if (dp[n][len + 1]) len++;
        }
}
int main(){
    int n;
    scanf("%d", &n);
    dp[1][1] = 1, dp[2][1] = 2; 
    for (int i = 3; i <= n; i++) work(i);
    for (int i = len; i >= 1; i--) printf("%d", dp[n][i]);
    return 0;
}

好的AC啦。

题目1：过河卒

也是简单的递归题，简单来说因为兵只能向右和向下走，我们反过来想就是从终点走回起点只能向上和向下，只要我们在每个点加上它下面的数字和右边的数字最后计算到1.1点就行了。

#pragma warning(disable:4996)
#include<stdio.h>
#define ull unsigned long long
int dx[9] = { 0, -2, -1, 1, 2, 2, 1, -1, -2 };
int dy[9] = { 0, 1, 2, 2, 1, -1, -2, -2, -1 };
int bx, by, mx, my;
unsigned long long ans[30][30];
bool book[30][30];
unsigned long long max(unsigned long long x, unsigned long long y) {return x > y ? x : y;}
int main() {
    scanf("%d%d%d%d", &bx, &by, &mx, &my);
    bx += 2; by += 2; mx += 2; my += 2;
    ans[2][2] = 1, book[mx][my] = 1;
    for (int i = 1; i <= 8; i++) book[mx + dx[i]][my + dy[i]] = 1;
    for (int i = 2; i <= bx; i++) {
        for (int j = 2; j <= by; j++) {
            if (book[i][j]) continue;
            ans[i][j] = max(ans[i][j], ans[i - 1][j] + ans[i][j - 1]);
        }
    }
    return 0 * printf("%llu\n", ans[bx][by]);
}

题目2：栈

如果考过408，那么应该都知道卡特兰数，这道题答案就是那个东西。但是这道题考的是递推的情况下，那么就得知道如何玩了。

2.1 没有元素的时候

当栈的元素没有的时候，出栈序列自然为null，当只有一个的时候，其出栈序列只有自身

2.2 N个元素的时候

当栈的元素有N个的时候（1,2,3,4，…，N），设x是当前出栈序列的最后一个（即为……X），我们可以将其分为两个部分，比X大的和比X小的。
其中比X小的数有X-1个，那么这些数全部出栈的个数为memo[x-1]；
比X大的数有n-x个，那么这些数全部出栈可能非memo[n-x]。
由乘法定理可知，这两个部分独立，故f[x]=f[x-1]*f[n-x]
最后只需要从0到n-1求和就可以，这就是卡特兰数的递推方式。

2.3 代码

#include <stdio.h>
int main(){
    int n, memo[20] = { 0 };
    scanf("%d", &n);
    memo[0] = 1, memo[1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 0; j < i; j++) memo[i] += memo[j] * memo[i - j - 1];
    return 0 * printf("%d\n", memo[n]);
}

另外由于递归需要使用系统栈，所以大部分的栈的题都可以递归完成。

题目3：数的计算

设当前数字为n。

要求1：不作任何处理

即自身需要计算一次，递推初始条件为1.

要求2：在它的左边加上一个自然数,但该自然数不能超过原数的一半

即我们在其左边加的数的数量就是加上n/2的具备此类性质的数量。

要求3：加上数后,继续按此规则进行处理,直到不能再加自然数为止

意味着我们只需要从不断的要么变为奇数或者使其除二之后加在当前数的左边就可以。

递推公式

因此我们得到了递推公式memo[i] = memo[i - 1] + memo[i / 2]（i为偶数）和memo[i] = memo[i - 1]（i为奇数）

代码

#include<stdio.h>
int memo[1005];
int main() {
    int n;
    scanf("%d", &n);
    memo[0] = memo[1] = 1;
    for (int i = 2; i <= n; i++){ 
        if (i & 1 == 0) memo[i] = memo[i - 1] + memo[i / 2];
        else memo[i] = memo[i - 1];
    }
    return 0 * printf("%d\n", memo[n]);
}

题目4：Function

简单的递归函数，注意算过的就别算直接用一个数组存起来，只需要注意边界条件即可（因为四个条件优先级依次降低，所以先写什么后写什么很重要）。

#include<stdio.h>
long long int memo[300][300][300];
long long int w(long long int a, long long int b, long long int c) {
    if (a <= 0 || b <= 0 || c <= 0) return 1;
    if (memo[a][b][c] != 0) return memo[a][b][c];
    else if (a > 20 || b > 20 || c > 20) memo[a][b][c]=w(20, 20, 20);
    else if (a < b&&b < c) memo[a][b][c]= w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    else memo[a][b][c]=w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
    return memo[a][b][c];
}
int main() {
    long long int a, b, c;
    do {
        scanf("%lld%lld%lld", &a, &b, &c);
        if (a == -1 && b == -1 && c == -1) return 0;
        else printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, w(a, b, c));
    } while (1);
    return 0;
}

题目5：外星密码

典型的递归题目，题目含义是展开字符串，而每一对[]都是一重展开，我们只需要：
0. 直接一边输入一遍计算；

1. 见到[就进入递归，结合输入的数字和字母直接展开并计入当前层的子串；
2. 见到]就返回当前层的子串让上一层相加即可；
3. 如果都不是，那么直接加到要返回到主函数的子串。

   #include<iostream>
   #include<string>
   using namespace std;
   string dfs(){
    int num;
    string s = "", Subs = "";
    char temp;
    while (cin >> temp){
        if (temp == '['){
            cin >> num;
            Subs = dfs();
            while (num--) s += Subs;
        }
        else{
            if (temp == ']') return s;
            else s += temp;
        }
    }
   }
   int main(){
    string ans = dfs();
    cout << ans << endl;
    return 0;
   }

题目6：蜜蜂路线

和楼梯一样的递推题，我们只需要知道递推公式怎么求就知道了；
首先我们知道，我们可以把第一层视作偶数，第二层视作奇数，那么实际上是一维数组，然后我们看到你能够从n-1和n-2来，所以就是走楼梯！只需要把走楼梯的代码拿来改改就是了。
但是这里问题来了，它输出的是一对，从n到m，这种情况下怎么办？
实际上这里的处理方式很简单，实际上fib数列在某种意义上也是一个前缀和数列（即每一个元素都包含了其之前的元素的某些信息的和，这个和不一定是直接累加，可能是其他），也就是说从n到m就是从0到m减去0到n的值就是我们得到的答案。
依旧要注意一下大数的处理方式。

#pragma warning(disable:4996)
#include<stdio.h>
int len = 1, dp[1050][1050];
void fib(int n) {
    for (int i = 1; i <= len; i++)
        dp[n][i] = dp[n - 1][i] + dp[n - 2][i];
    for (int i = 1; i <= len; i++)
        if (dp[n][i] > 9) {
            dp[n][i + 1] += dp[n][i] / 10;
            dp[n][i] = dp[n][i] % 10;
            if (dp[n][len + 1]) len++;
        }
}
int main() {
    int n, m;
    scanf("%d%d", &m, &n);
    dp[1][1] = 1, dp[2][1] = 2;
    for (int i = 3; i <= n - m; i++) fib(i);//注意循环的条件
    //如果你枚举到n的话那么len记录的是n的长度不是n-m的长度，会导致前导0而WA
    for (int i = len; i >= 1; i--) printf("%d", dp[n - m][i]);
    return 0;
}

题目7：小A点菜

题目看起来是简单的0/1背包问题，就是M的包最多能装多少的东西，但是这里问的是种数，所以我们得转换一下思路。
首先我们定义dp[i][j]为第i道菜用了j元，那么我们会得到一下几个转移方程（记菜价为price[i]，答案在dp[][]中）

if(price[i]==j) dp[i][j]=dp[i-1][j] + 1；

if(price[i]<j) dp[i][j]=dp[i-1][j-price[i]];

if(price[i]>j) dp[i][j]=dp[i-1][j]+dp[i-1][j-price[i]];

这三种的解释是，如果钱够，那么方法就是吃这道菜和不吃这道菜的方法和，但是不够，那么我们就只能吃前i-1道菜的方法了。
但是这道题和背包很相似，所以我们考虑下能不能降维，从后往前循环的情况，钱始终是够的时候才进入循环，这样三个条件变为了钱是否够一个条件，且剩下的钱满足单调性，可以满足一维dp的情况，这个时候的dp方程为

dp[j] = dp[j] + dp[j - price[i]]

最后我们可以得到下面的代码

#pragma warning(disable:4996)
#include<stdio.h>
int price[110], dp[100050];
int main(){
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int n, m;
    dp[0] = 1;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &price[i]);
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= price[i]; j--) dp[j] = dp[j] + dp[j - price[i]];
    return 0 * printf("%d\n", dp[m]);
}

题目8：选数

原题，略

题目9：覆盖墙壁

这道题也是一个递推的题，只不过特别考验分类讨论能力。这里定义 L形砖，1形砖和一形砖。

当最后一列需要被1形砖排列的时候

这种时候我们的方案数目实际上适合倒数第二列的的状态是一样的，因为这种情况下最后只能由1形砖来填充。

当最后两列由两块一形砖的时候

这种时候我们的方案是倒数第三列的状态是一致的，因为我们无法填充L型转，也无法使用1形砖（因为在上面我们已经讨论了1形砖，再次讨论整个集合就重复了）

定义上述两种平凡情况记录为one数组，则总的方案数为one[n]=one[n-1]+one[n-2]。

当最后一个需要用L形状砖块的时候

由于不能使最后一列有空格，所以必然是由L的竖着或者横着一部分填充列，这个时候我们得分为两个状态：即为（第一列0 0 1 1第二列0 0 0 1）和（第一列 0 0 0 1 第二列0 0 1 1 ）两个状态；这个时候我们的填充方式有两种，分别是使用中心对称的L来填充或者再加个一形砖使得变为相对的另外一种状态。
定义此类状态为L数组
故可以得到L[n-2]=one[n-3]（使用中心对称的L）+2 * L[n-3]（使用一形砖块，且分为上下两部分），即one[n]=one[n-1]+one[n-2]+2 * L[n-2]，L[n]=one[n-1]+L[n-1]。
以上就是总的递推方程，最后注意取模就行了。

代码

#include<stdio.h>
const int MAXN = 1000050;
const int Mod = 10000;
int one[MAXN], L[MAXN];
int main(){
    int n;
    scanf("%d",& n);
    one[0] = one[1] = L[1] = 1;
    for (int i = 2; i <= n; i++){
        one[i] = ((one[i - 1] + one[i - 2]) % Mod + 2 * L[i - 2] % Mod) % Mod;
        L[i] = (L[i - 1] + one[i - 1]) % Mod;
    }
    return 0 * printf("%d\n", one[n]);
}

题目10：Secret Cow Code S

题目的意思是ABC变为CAB变为BCA一直循环拼成一个无穷长串，我们找到这个串的第n位。那么这道题可以暴力做出来一部分数据点，但是10^18注定会卡时间。所以需要考虑其他的。

假设串为ABC，那么无穷循环后是ABCCAB，我们发现倍增之后[1,2]和[5,6]是相同的；接着考虑串为ABCDEFFABCDE，串的[1,5]和[8,12]是相同的

我们对ABC拓展三次有ABCCABBABCCA，这样发现了规律，每次倍增之后前部分记为S1，后半部分记为S2，那么每次对S2来说来自于S1向后移1位得到，当i-1=0时，且S2[i]=S1[i-1]的时候，我们可以很容易得到得到i的大小为S1[l/2]处。

于是这里可以分治一波，我们每发现当前的临时串长比输入的n小的时候，我们把临时串长倍增，然后一直循环知道临时串长大于n；

之后再是临时串长倍减然后开始循环：当temp_len大于串长的时候，我们进入循环后，检验n是否大于临时串长，大于了之后就减掉temp_len，然后看n为多少，如果n为0就变为最大值-1，否则n–。如果n比temp_len小，templen直接减半。这样处理了之后，s[n%len]即为答案。

#include<iostream>
#include<string>
using namespace std;
int main() {
    string s;
    long long n, temp_len = 1, len;
    cin >> s >> n;
    len = s.length();
    for (temp_len = len; temp_len <= n; temp_len <<= 1);
    temp_len >>= 1;
    n -= 1;
    while (temp_len >= len) {
        if (n >= temp_len) {
            n -= temp_len;
            if (n == 0) n = temp_len - 1;
            else n--;
        }
        temp_len >>= 1;
    }
    cout << s[n % len] << endl;
    return 0;
}

题目11：黑白棋移动

我们能够很明显的发现前面的规律，奇数步骤都是前面o和的交界处和–交换，而偶数行都是**和–交换，但是到了最后四行就不一样了，于是找不到规律的情况下，我这里打了个表。
那么问题来了，为什么后面四行没有规律呢，实际上我的理解是，如果继续如此迭代下去的话，那么最后的步骤会强制变为o–ooo*…..那么久不满足了每次必须跳过若干棋子的要求，因此必须使用题目sample的要求。

#include<iostream>
#include<string>
using namespace std;
string Last_4[4] = { "ooo*o**--*", "o--*o**oo*", "o*o*o*--o*", "--o*o*o*o*" }, temp;
char memo[250];
void swap(char& a, char& b){
    char t = a;
    a = b;
    b = t;
}
void move(int start, int end){
    swap(memo[start], memo[end]);
    swap(memo[start + 1], memo[end + 1]);
}
int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        memo[i] = 'o';
    for (int i = n; i < 2 * n; i++)
        memo[i] = '*';
    memo[2 * n] = memo[2 * n + 1] = '-';
    for (int i = 0; i < 2 * n + 2; i++) 
        cout << memo[i];
    cout << endl;
    int len = n;
    while (1){
        move(len - 1, 2 * len);
        for (int i = 0; i < 2 * n + 2; i++) 
            cout << memo[i];
        cout << endl;
        len--;
        if (len == 3) break;
        move(len, 2 * len);
        for (int i = 0; i < 2 * n + 2; i++) 
            cout << memo[i];
        cout << endl;
    }
    for (int i = 0; i < n - 4; i++) 
        temp += "o*";
    for (int i = 0; i < 4; i++) 
        cout << Last_4[i] << temp << endl;
    return 0;
}

题目12：幂次方

如果你知道计算机的表示中所有的数实际上都是由二进制转换，那么这道题就很好做了，每位弄一个掩码，然后求出来对应所在位，然后再递归即可，递归边界为0，那么返回的是0（1为2^0）。

#include<iostream>
#include<string>
using namespace std;
string Decomposition(int n) {
    int i = 0;
    string ans = "";
    if (n == 0) return string("0");
    do {
        if (n & 1) {
            string ans_left, ans_right;
            if (i == 1) ans_left = "2";
            else ans_left = "2(" + Decomposition(i) + ")";
            if (ans == "") ans_right = "";
            else ans_right = "+";
            ans = ans_left + ans_right + ans;
        }
        i++;
    } while (n >>= 1);
    return ans;
}
int main() {
    int n;
    cin >> n;
    string ans = Decomposition(n);
    cout << ans << endl;
    return 0;
}

题目13： 地板填补

比较单纯的递归题:
只需要判断公主所在的点是当前中点的相对位置的那个部分（以公主为原点，分为左上左下右上右下），然后进入对应方向递归即可。
但是公主的点是不覆盖地毯的，你这样的话其他三个方向的怎么铺地毯呢？实际上我们只需要选择任意一个可以和公主组合成一个正四边形的地毯，这样就可以模拟为四个方向都有一个公主的情况，这样就可以全部覆盖了。

#include<stdio.h>
void dfs(long long cur_x, long long cur_y, long long x_start, long long y_start, long long len){
    if (len == 1) return;
    if (cur_x - x_start <= len / 2 - 1 && cur_y - y_start <= len / 2 - 1){//左上
        printf("%lld %lld 1\n", x_start + len / 2, y_start + len / 2);
        dfs(cur_x, cur_y, x_start, y_start, len / 2);
        dfs(x_start + len / 2 - 1, y_start + len / 2, x_start, y_start + len / 2, len / 2);
        dfs(x_start + len / 2, y_start + len / 2 - 1, x_start + len / 2, y_start, len / 2);
        dfs(x_start + len / 2, y_start + len / 2, x_start + len / 2, y_start + len / 2, len / 2);
    }
    else if (cur_x - x_start <= len / 2 - 1 && cur_y - y_start > len / 2 - 1){//左下
        printf("%lld %lld 2\n", x_start + len / 2, y_start + len / 2 - 1);
        dfs(x_start + len / 2 - 1, y_start + len / 2 - 1, x_start, y_start, len / 2);
        dfs(cur_x, cur_y, x_start, y_start + len / 2, len / 2);
        dfs(x_start + len / 2, y_start + len / 2 - 1, x_start + len / 2, y_start, len / 2);
        dfs(x_start + len / 2, y_start + len / 2, x_start + len / 2, y_start + len / 2, len / 2);
    }
    else if (cur_x - x_start > len / 2 - 1 && cur_y - y_start <= len / 2 - 1){//右上
        printf("%lld %lld 3\n", x_start + len / 2 - 1, y_start + len / 2);
        dfs(x_start + len / 2 - 1, y_start + len / 2 - 1, x_start, y_start, len / 2);
        dfs(x_start + len / 2 - 1, y_start + len / 2, x_start, y_start + len / 2, len / 2);
        dfs(cur_x, cur_y, x_start + len / 2, y_start, len / 2);
        dfs(x_start + len / 2, y_start + len / 2, x_start + len / 2, y_start + len / 2, len / 2);
    }
    else{//右下
        printf("%lld %lld 4\n", x_start + len / 2 - 1, y_start + len / 2 - 1);
        dfs(x_start + len / 2 - 1, y_start + len / 2 - 1, x_start, y_start, len / 2);
        dfs(x_start + len / 2 - 1, y_start + len / 2, x_start, y_start + len / 2, len / 2);
        dfs(x_start + len / 2, y_start + len / 2 - 1, x_start + len / 2, y_start, len / 2);
        dfs(cur_x, cur_y, x_start + len / 2, y_start + len / 2, len / 2);
    }
}
int main(){
    long long x, y, k, len = 1;
    scanf("%lld %lld %lld", &k, &x, &y);
    for (int i = 1; i <= k; ++i) len *= 2;
    dfs(x, y, 1, 1, len);
    return 0;
}

题目14：南蛮图腾

和分型一样的典型递归题，但是这里由于输出的不同，我们既可以考虑从小到大，也可以考虑从大到小.。
从小到大就是我们存一个在最开始的地方存一个三角形，然后我们就在他最左下角的左下方和最右下角的右下方开始copy一个自己，每次注意每次递增和初始化问题即可。
这里采用位运算来加速过程，实际上你就理解为pow(2,x)即可。

#pragma warning(disable:4996)
#include<stdio.h>
char output[1050][1050];
int main() {
    int n, len = 4, temp = 1;
    scanf("%d", &n);
    for (int i = 0; i < 1050; i++)
        for (int j = 0; j < 1050; j++) output[i][j] = ' ';
    //上面的初始化是坑，虽然本地输出是一样的，如果不初始化的话在匹配的时候是WA掉的
    if (n == 1) return 0 * printf(" /\\\n/__\\\n");
    //接下里我们初始化一个标准三角形
    output[1 << n][1] = '/', output[1 << n][2] = '_', output[1 << n][3] = '_', output[1 << n][4] = '\\';
    output[(1 << n) - 1][2] = '/', output[(1 << n) - 1][3] = '\\';
    while (temp < n){
        for (int i = (1 << n); i > ((1 << n) - (1 << temp)); i--)
            for (int j = 1; j <= len; j++){
                output[i][j + (1 << (temp + 1))] = output[i][j];    
                output[i - (1 << temp)][j + (1 << temp)] = output[i][j];
            }
        temp++, len = len << 1;
    }
    /*
    如果你想要从小到大，你甚至可以这么玩
    output[1][1] = '/'; output[1][2] = '\\';
    output[2][1] = '/'; output[2][2] = '_'; output[2][3] = '_'; output[2][4] = '\\';
    int len = 1;
    for (int i = 2; i <= n; i++){
        for (int j = 1; j <= len; j++){
            len <<= 1;
            int end_pos = j * 2;
            for (int k = 1; k <= end_pos; k++)
                output[len + j][k] = output[j][k];
            for (int k = end_pos + 1; k <= 2 * (len + j - end_pos); k++)
                output[len + j][k] = ' ';
            for (int k = 2 * (len + j) - end_pos + 1; k <= 2 * (len + j); k++)
                output[len + j][k] = output[j][k + end_pos - 2 * (len + j)];
        }
    }
    len <<= 1;
    */
    for (int i = 1; i <= (1 << n); i++){
        for (int j = 1; j <= (1 << (n + 1)); j++) printf("%c", output[i][j]);
        printf("\n");
    }
    return 0;
}

递推结束，下一个题单是贪心，听着最简单，证明起来最困难的东西。