Day 17 · 递推与记忆化

题意：给定一个三参数的递归函数 w(a,b,c)，按四条规则计算它的值。输入若干组 (a,b,c)，每组输出一行 w(a, b, c) = 答案，读到 -1 -1 -1 结束。

四条规则按顺序判断（顺序是关键）：

1. 只要 a ≤ 0 或 b ≤ 0 或 c ≤ 0 → 返回 1
2. 否则，只要 a > 20 或 b > 20 或 c > 20 → 返回 w(20, 20, 20)
3. 否则，如果 a < b 并且 b < c → 返回 w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)
4. 否则 → 返回 w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1)

思路

这就是一个标准的记忆化搜索。三个参数的范围被规则压到 1~20，状态总数只有 20³ = 8000 个 —— 但因为裸递归的分支是 3~4 路，重复量巨大，不加缓存必 TLE。

加上 memo[a][b][c] 之后，每个状态最多真正计算一次，剩下的全是 O(1) 查表。

1 1 1
2 2 2
-1 -1 -1

w(1, 1, 1) = 2
w(2, 2, 2) = 4

完整代码

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

// memo[a][b][c] 存已经算过的答案，-1 表示还没算过
// 因为 a,b,c 超过 20 会先被截断到 20，所以只需要开 0..20
long long memo[21][21][21];

long long w(long long a, long long b, long long c){
    // 第 1 条规则：只要有一个 <= 0 就返回 1（必须放在最前面判断）
    if(a <= 0 || b <= 0 || c <= 0) return 1;
    // 第 2 条规则：只要有一个 > 20 就全部截断到 20
    if(a > 20 || b > 20 || c > 20) return w(20, 20, 20);

    // ★ 记忆化的核心：算过就直接取，不再递归
    if(memo[a][b][c] != -1) return memo[a][b][c];

    long long res;
    if(a < b && b < c){
        res = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    }else{
        res = w(a - 1, b, c) + w(a - 1, b - 1, c)
            + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
    }

    memo[a][b][c] = res;   // ★ 存下来，下次 O(1) 取用
    return res;
}

int main(){
    memset(memo, -1, sizeof(memo));   // -1 的二进制是全 1，long long 也适用

    long long a, b, c;                // ★ 必须 long long，输入范围是整个 long long
    while(cin >> a >> b >> c){
        if(a == -1 && b == -1 && c == -1) break;
        cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << "\n";
    }
    return 0;
}

w(1, 1, 1) = 2
w(2, 2, 2) = 4

易错点

• 规则顺序写反：先判 >20 再判 ≤0，w(30,-1,0) 就错了。必须严格按题面从上到下。
• 用 int 读输入：输入可能到 ±9.2×10¹⁸，int 直接溢出。必须 long long。
• memo 数组开小了：memo[20][20][20] 的下标只到 19，访问 memo[20][20][20] 就越界。要么开 21，要么开 25 留余量。
• 忘了初始化成 −1：全局数组默认是 0，那么「没算过」和「答案是 0」就分不清了。
• 输出格式：必须是 w(a, b, c) = ans，逗号后面有空格、等号两边有空格，一个都不能少。
• 用 endl 换行：10⁵ 行输出会慢很多，用 "\n"。

题意：题面给了一个看起来很吓人的公式

F_n = [ ((1+√5)/2)ⁿ − ((1−√5)/2)ⁿ ] / √5

让你输入 n，输出 Fn，保留两位小数。

思路

用「滚动两个变量」的递推：只保留 F(i−2) 和 F(i−1)，一路往后推。这样连数组都不用开。

最后输出时把 long long 转成 double 用 printf("%.2f") 打两位小数。因为答案本身是整数，所以小数部分永远是 .00。

6

8.00

完整代码

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

int main(){
    int n;
    cin >> n;

    // F(n) 就是斐波那契数列：F(0)=0, F(1)=1
    // n <= 48 时 F(48) = 4807526976，已经超过 int 上限，必须用 long long
    long long f0 = 0, f1 = 1;   // f0 = F(i-2), f1 = F(i-1)

    if(n == 0){
        printf("0.00\n");
        return 0;
    }

    for(int i = 2; i <= n; i++){
        long long t = f0 + f1;   // F(i) = F(i-1) + F(i-2)
        f0 = f1;
        f1 = t;
    }

    // 题目要求保留两位小数，答案本身是整数，所以小数为 .00
    printf("%.2f\n", (double)f1);
    return 0;
}

易错点

• 用 int 存答案：n = 47 开始就溢出成负数了。这是本题第一号杀手。
• 被公式吓住：看到 √5 和 n 次方就想去写 pow(sqrt(5), ...)，结果浮点误差导致答案差 0.01。直接用斐波那契递推最稳。
• n = 0 没特判：如果写成「先循环再输出」，n=0 时 f0/f1 的处理容易出错。老老实实写个 if(n == 0)。
• 输出格式：必须保留两位小数，写成 cout << f1 输出 8 是错的，要输出 8.00。

题意：蜂房排成一条锯齿形的编号链（1、2、3……），蜜蜂只能从小编号爬到大编号的相邻蜂房。问从蜂房 m 爬到蜂房 n（m < n）有多少条不同路线。

思路：又是一只「兔子」

先看图找规律。仔细观察蜂房的连接方式会发现：编号为 i 的蜂房，只能直接通到 i+1 和 i+2。

那么「到达 i 号蜂房的路线数」dp[i]，只能从这两个方向来：

• 从 i-1 迈一步过来 → dp[i-1] 条
• 从 i-2 跳两步过来 → dp[i-2] 条

dp[i] = dp[i - 1] + dp[i - 2]      // 又是斐波那契！

初值：起点 dp[m] = 1（站在起点算 1 种走法），dp[m+1] = 1（只能一步迈过去）。

所以答案就是 F(n − m + 1)（斐波那契的写法是 F(1)=1, F(2)=1）。

第一个版本：long long 递推（能过样例，但过不了全部数据）

#include <iostream>
using namespace std;

// 蜜蜂只能从小编号爬到相邻的大编号蜂房，
// 所以 dp[i] = dp[i-1] + dp[i-2]，这就是斐波那契
// 起点 dp[m] = 1，dp[m+1] = 1，答案就是 dp[n] = F(n-m+1)
int main(){
    int m, n;
    cin >> m >> n;

    long long a = 1, b = 1;   // a = dp[i-2], b = dp[i-1]；第一步时两者都是 1

    for(int i = m + 2; i <= n; i++){
        long long t = a + b;
        a = b;
        b = t;
    }

    cout << b << endl;
    return 0;
}

第二个版本：高精度加法（可以 AC）

思路：用一个 vector<int> 从低位到高位存每一位数字，然后手动模拟小学竖式加法。

#include <iostream>
#include <vector>
using namespace std;

// 高精度加法：用 vector 存每一位（下标 0 是最低位），手动处理进位
vector<int> addBig(const vector<int>& A, const vector<int>& B){
    vector<int> C;
    int carry = 0;                            // 进位
    for(size_t i = 0; i < A.size() || i < B.size() || carry; i++){
        int s = carry;
        if(i < A.size()) s += A[i];
        if(i < B.size()) s += B[i];
        C.push_back(s % 10);                  // 本位留下
        carry = s / 10;                       // 进位带走
    }
    return C;
}

int main(){
    int m, n;
    cin >> m >> n;

    vector<int> a(1, 1), b(1, 1);   // a = dp[i-2], b = dp[i-1]

    for(int i = m + 2; i <= n; i++){
        vector<int> t = addBig(a, b);
        a = b;
        b = t;
    }

    // 从最高位往低位输出
    for(int i = (int)b.size() - 1; i >= 0; i--) cout << b[i];
    cout << endl;
    return 0;
}

1 14

377

易错点

• 只写 long long 版就交：样例能过，但 n − m + 1 ≥ 93 的测试点全部 WA。这题必须高精度。
• 初值给错：起点要设为 1（站在起点算一种走法），dp[m+1] 也是 1。都设成 0 会输出 0。
• 循环边界：循环应该从 m+2 开始到 n 结束。写成从 1 开始推会在 m 很大时出错。
• 高精度输出方向：vector 里下标 0 是最低位，输出必须从后往前，倒着输出就得到镜像数了。
• 忘记处理进位：s = 10 时要留 0 进 1，只取 s % 10 不更新 carry 会丢位。

题意：有一个操作数序列 1, 2, …, n，栈 A 的深度大于 n。你可以做两种操作：

1. 把操作数序列头端的数压进栈（push）
2. 把栈栈顶的数弹到输出序列尾端（pop）

问：通过任意组合这些操作，一共能得到多少种不同的输出序列？

思路：按「最后一个出栈的是谁」分类

设 f[i] 表示「i 个数进栈能得到的输出序列数」。现在来想 i 个数的情况。

不管过程怎么乱，最后出栈的那一个数一定是某个特定的数。假设它是第 j+1 个进栈的 （j 从 0 到 i−1），那么整个过程被它切成互不干扰的两段：

• 它进栈之前，已经有 j 个数进栈并且全部先出去了 → 有 f[j] 种
• 它进栈之后，剩下的 i−1−j 个数进进出出，最后才轮到它 → 有 f[i-1-j] 种

两段相互独立，乘起来；j 的所有取值加起来，就是全部：

手算一遍前几项验证一下：f[1]=1, f[2]=2, f[3]=5 —— 和题目样例 n=3 → 5 对上了。

3

5

完整代码

#include <iostream>
using namespace std;

// 卡特兰数：f[i] = Σ(j=0..i-1) f[j] * f[i-1-j]，边界 f[0] = 1
// n <= 18 时 Catalan(18) = 477638700，用 long long 保险
int main(){
    int n;
    cin >> n;

    long long f[25] = {0};
    f[0] = 1;                       // ★ 空序列算 1 种，这是递推的种子

    for(int i = 1; i <= n; i++){
        for(int j = 0; j < i; j++){
            f[i] += f[j] * f[i - 1 - j];   // ★ 两段方案数相乘
        }
    }

    cout << f[n] << endl;
    return 0;
}

long long c = 1;
for(int i = 1; i <= n; i++)
    c = c * (n + i) / i;      // 先算出 C(2n, n)
cout << c / (n + 1) << endl;  // 再除以 n+1

易错点

• f[0] 忘了置 1：这样 f[1] 算出来就是 0，后面全废。空序列（一个数都不进）也算 1 种方案。
• 双重循环边界写错：内层是 j < i（不是 j <= i），因为是 i−1−j，j 最大只能到 i−1。
• 用 int 存 f 数组：虽然 n=18 的答案 477638700 刚好塞得下 int，但习惯上用 long long 更稳（很多卡特兰数题 n 稍大就爆）。
• 越界：f[25] 够用（n ≤ 18），但注意别写成 f[20] 再访问 f[18] —— 那正好卡在边界上，容易出错。
• 组合数公式版乘除顺序颠倒：必须 * 在前 / 在后，写成 c / i * (n+i) 会丢精度。