P4741 数的计数（基础）

解题思路

题目说：有一个自然数 n，可以"不做任何处理"，也可以在左边加一个自然数，但加的数不能超过原数的一半；加完之后，还可以继续加。问一共能得到多少种数（包括 n 自己）。

例如 n=6：能得到的数是 6、16、26、126、36、136，一共 6 个。我们可以总结出规律：设 f(n) 表示以 n 开头的数的个数（包括 n 本身）。那么 f(n)=1+f(1)+f(2)+…+f(⌊n/2⌋)。为什么？因为 n 自己算 1 种；如果在左边加上 i（i 从 1 到 n/2），得到的新数开头就变成了 i，后面还能继续加，所以再加上 f(i)。

例如 f(6)=1+f(1)+f(2)+f(3)=1+1+2+2=6，和例子一致。注意这里的 f 有点特别：f(1)=1（只有"1"），f(2)=1+f(1)=2（2 和 12），f(3)=1+f(1)=2（3 和 13）。

注意 n≤1000，如果用普通递归，f(1000) 会重复计算很多次 f(小值)，非常浪费。所以用"记忆化"：用一个数组 f[1005] 把算过的结果存起来，如果 f[n] 已经算过了，直接返回，不用再算。这样每个数最多算一次，速度非常快。

边界情况：n=1 时，f(1)=1，只有"1"本身一种。输出的是满足条件的数的个数，不是把每个数列出来。

参考代码

// 数的计数：记忆化递归统计满足条件的数的个数
#include <iostream>

int f[1005];

int cnt(int n) {
    if (f[n]) return f[n];
    int s = 1;               // 先算上自己本身
    for (int i = 1; i <= n / 2; i++) s += cnt(i);  // 左边加不超过一半的数
    return f[n] = s;
}

int main() {
    int n;
    std::cin >> n;
    std::cout << cnt(n) << "\n";
    return 0;
}

复杂度分析

因为用了记忆化数组，每个 f(n) 只会被真正计算一次，计算 f(n) 时要循环 n/2 次。总共对 n 个不同值计算，所以时间复杂度约为 O(n²)，当 n=1000 时大约 50 万次加法，一秒内轻松完成。空间上只需要一个大小 1005 的数组，是 O(n) 的，非常小。如果不做记忆化，普通递归会重复计算导致变慢，所以记忆化是这道题的关键。