P4752 数的个数2（基础）

解题思路

这道题是一个"给数字排队"的游戏。我们手里有一个数字 n，可以不断在它的左边加上一个"不超过原数一半的奇数"，加完之后还可以继续加，一直加到不能再加为止。问：这样一共能得到多少个不同的数？注意，原来的 n 本身也算一个。

比如 n = 11 时，能得到 6 个数：11、1 11、3 11、5 11、1 3 11、1 5 11。

为什么是这 6 个？因为 11 的一半是 5，左边的奇数只能是 1、3、5。加上 1 之后得到"1 11"，还可以继续往 1 的左边加不超过 1 一半（也就是 0）的奇数，没有奇数可加了；但如果左边加的是 3，得到"3 11"，还可以继续往 3 的左边加不超过 1 的奇数（也就是 1），得到"1 3 11"。按照这个规则一个个数下去，一共就是 6 个。

用递归来想：定义一个函数 f(n)，表示"以 n 开头（或者说当前最前面的数是 n）一共能组成多少个不同的数"。f(n) 至少是 1，因为 n 自己算一个。然后，所有不超过 n 一半的奇数 i（1、3、5...）都可以放在 n 的左边，放上之后还能继续得到 f(i) 种情况。所以：

f(n) = 1 + f(1) + f(3) + f(5) + ... （只加到不超过 n/2 的奇数为止）

边界情况：n = 1 时，1 的一半是 0，没有奇数可以加，所以 f(1) = 1。

这里有个小技巧：直接递归会重复算很多次（比如算 f(11) 和 f(13) 都会用到 f(5)），所以用一个数组 ans 把算过的结果记下来，下次直接查表，这就是"记忆化"，让程序跑得飞快。题目保证输入的 n 是奇数，我们放心按规则做即可。

参考代码

// 数的个数2：左边加一个不超过原数一半的奇数，统计满足条件数的个数
#include <iostream>
using namespace std;

long long ans[1005];   // 记忆化数组：ans[n]保存f(n)的答案，避免重复计算

// 递归求以n开头能得到的数的个数：本身算1个，再加左边放奇数1、3、5...的情况
long long f(int n) {
    if (ans[n] > 0) return ans[n];          // 算过就直接返回
    long long s = 1;                        // 不作处理：n本身算一个
    for (int i = 1; i <= n / 2; i += 2) {   // 左边只能加奇数且不超过n的一半
        s += f(i);                          // 加上后继续按规则处理
    }
    return ans[n] = s;
}

int main() {
    int n;
    cin >> n;
    cout << f(n) << endl;
    return 0;
}

复杂度分析

有了记忆化之后，每个奇数 n 只会真正计算一次，每次计算要枚举不超过 n/2 的奇数，大约 n/4 个。所以总时间约为 O(n²)。n < 100，最多 100² = 10000 次运算，非常轻松。数组 ans 只用了 1005 个格子，空间 O(n)。用 long long 类型存放结果，即使答案很大也不怕装不下。