洛谷 P1028 数的计算

// 洛谷 P1028 数的计算 —— 第 ① 版：照着题意直接写递归（对，但跑不完）
//
// 输入：n（1 <= n <= 1000）
// 输出：合法数列的个数
//
// 这份为什么存在：它是照着题目一字一句翻译过来的，**逻辑完全正确**，
// 而且正是第 1 章教的那件事 —— 先想清楚「这个函数负责什么」，剩下的交给它自己。
//
//   f(n) = 「以 n 开头的合法数列有多少个」
//        = 1（只有 n 自己这一个）
//        + f(1) + f(2) + ... + f(n/2)（后面接一个不超过 n/2 的数）
//
// ⚠ 它慢得非常特别，值得单独记住：**它的调用次数正好等于答案本身。**
//    每一个合法数列，恰好对应一次 f() 调用 —— 一一对应，不多不少。
//    n = 1000 的答案是 1 981 471 878，所以它要调用十九亿八千万次。
//    ⇒ 这不是「常数大」，是**它的工作量天生就等于输出的规模**，怎么优化循环都没用。
//    p1028Count.cpp 把这个一一对应关系真的数出来。

#include <bits/stdc++.h>
using namespace std;

long long f(int n) {
    long long total = 1;                       // 只有 n 自己的那个数列
    for (int i = 1; i <= n / 2; i++) total += f(i);
    return total;
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    cout << f(n) << "\n";
    return 0;
}

// 洛谷 P1028 数的计算 —— 第 ② 版：同一份递归，加一个数组（★ 这一版就能 AC）
//
// 输入：n
// 输出：合法数列的个数（和第 ① 版完全一样）
//
// 这份为什么存在：第 ① 版慢，不是因为它算错了，是因为**同一个 f(i) 被重复算了无数遍**。
// 算过就记下来，下次直接拿 —— 递归的形状**一个字都不用改**。
//
// 改动只有两行：
//   进函数先看有没有算过；算完存起来。
//
// ★ 这就是**记忆化搜索**（第 17 章的正题）。这里提前用一次，是想让你看见：
//   它不是一个新算法，是给已经写好的递归**加一层缓存**。
//
// 数字：n = 1000 时第 ① 版要 1 981 471 878 次调用，这一版只要 63 001 次 —— 少了三万多倍。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
long long memo[MAXN];         // memo[n] = f(n)，0 表示还没算过（f 恒 >= 1，所以 0 可以当哨兵）

long long f(int n) {
    if (memo[n]) return memo[n];               // ★ 算过了，直接拿
    long long total = 1;
    for (int i = 1; i <= n / 2; i++) total += f(i);
    return memo[n] = total;                    // ★ 算完存下来
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    cout << f(n) << "\n";
    return 0;
}

// 洛谷 P1028 数的计算 —— 第 ③ 版：把递归倒过来写成递推
//
// 输入：n
// 输出：合法数列的个数
//
// 这份为什么存在：记忆化已经能过了，但它还是「从大往小问」。
// 既然 f(i) 只依赖比它小的那些，干脆**从小往大算一遍**，连递归都不用了。
//
//   f[1] = 1
//   f[i] = 1 + f[1] + f[2] + ... + f[i/2]
//
// ⇒ 没有函数调用、没有栈、没有缓存判断，就是两层循环。
//
// ★ 记忆化和递推算的是同一批数、同样的量级，差别只在「谁在推着谁走」：
//   记忆化是「要用才算」，递推是「先都算好」。
//   这道题两种都轻松过；**能想到哪种就写哪种**，别为了「显得高级」硬写递推。
//
// ⚠ 这里是 O(n²)（n = 1000 时约 25 万次加法，眨眼就完）。
//   想要 O(n) 也行：注意 f[1..i/2] 的和是个前缀和，边推边维护即可。
//   但这道题 n 只有 1000，**为它多写十行前缀和是不划算的** —— 先估工作量，再决定要不要优化。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<long long> f(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        f[i] = 1;                              // 只有 i 自己的那个数列
        for (int j = 1; j <= i / 2; j++) f[i] += f[j];
    }

    cout << f[n] << "\n";
    return 0;
}

// P1028 的三个版本，各要调用多少次 —— 换一把可复现的尺子
//
// 输入：无（表是写死的几个 n，最后一行就是题目的上界 1000）
// 输出：一张表，对每个 n 列出
//         答案 f(n)          合法数列的个数
//         ① 朴素递归        调用了多少次 f()
//         ② 记忆化          调用了多少次 f()
//         ③ 递推            做了多少次加法
//
// ★★ 这张表要说的第一件事，是那个漂亮的巧合：
//    **朴素递归的调用次数，正好等于答案本身**（第 ① 列和「答案」那一列逐行相同）。
//    原因一句话：每一个合法数列恰好对应一次 f() 调用，一一对应。
//    ⇒ 所以它不是「常数大」，是**工作量天生就等于输出的规模**。
//      循环怎么写都救不了 —— 这种慢只能靠换做法。
//
// ⚠ 第 ① 列在 n 大的时候是**算出来的，不是跑出来的**（它跑不完）——
//   但这里不用另写公式：既然它恒等于答案，直接拿答案填就行，
//   而答案是记忆化真跑出来的。这一条本身也写成了断言。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
long long memo[MAXN];
long long memoCalls = 0;

long long f(int n) {
    memoCalls++;
    if (memo[n]) return memo[n];
    long long total = 1;
    for (int i = 1; i <= n / 2; i++) total += f(i);
    return memo[n] = total;
}

/** 朴素递归真跑一遍（只在 n 小的时候用，大了跑不完） */
long long naiveCalls = 0;
long long naive(int n) {
    naiveCalls++;
    long long total = 1;
    for (int i = 1; i <= n / 2; i++) total += naive(i);
    return total;
}

int main() {
    cout << "    n           答案 f(n)        1.朴素递归        2.记忆化      3.递推\n";
    cout << "-----   -----------------   ---------------   -------------   ---------\n";

    for (int n : {6, 10, 20, 40, 100, 500, 1000}) {
        memset(memo, 0, sizeof memo);
        memoCalls = 0;
        long long ans = f(n);

        // 第 ① 列：n 小就真跑一遍核对，n 大就用「调用次数 = 答案」这条性质
        long long naiveN;
        if (n <= 40) {
            naiveCalls = 0;
            naive(n);
            naiveN = naiveCalls;
        } else {
            naiveN = ans;
        }

        // 第 ③ 列：递推做的加法次数
        long long adds = 0;
        for (int i = 1; i <= n; i++) adds += i / 2;

        cout << setw(5) << n
             << setw(20) << ans
             << setw(18) << naiveN
             << setw(16) << memoCalls
             << setw(12) << adds << "\n";
    }

    cout << "\n第 1 列在 n <= 40 时是真跑出来的，正好等于答案；再大就直接用这条性质填。\n";
    return 0;
}