1304 数的计数
大约 5 分钟
1304 数的计数
【算法】 递推、递归、前缀和
【C++】 一维数组、前缀和、unsigned long long
【难度】 入门
一、题目简述
给定自然数 (),按以下规则不断生成新数:
- 不做任何处理(原数本身就计入答案)
- 在它左边加上一个自然数,但这个数不能超过原数的一半
- 加完后,继续对新的最左边部分递归处理,直到不能再加为止
问:一共能生成多少个不同的数(包括 本身)?
样例: 时,可以生成 6 个数:
6
16
26
126
36
136二、解题思路
2.1 手动模拟
用一棵树来表示所有生成路径:
6 ← 原数,计入
├── 1|6 (1 ≤ 6/2=3) ← 左边加 1
│ └── 1 无法再拆分
├── 2|6 (2 ≤ 3) ← 左边加 2
│ └── 1|26 (1 ≤ 2/2=1) ← 对 2 继续拆分
└── 3|6 (3 ≤ 3) ← 左边加 3
└── 1|36 (1 ≤ 3/2=1) ← 对 3 继续拆分共 6 个叶子节点,即 6 种合法结果。
2.2 关键观察
给 左边加上 ()后, 成为新的最左边部分。后续能否继续加数,完全取决于 还能拆多少。
设 表示从 出发能生成的数的总数。那么:
- 第一项 : 本身
- 求和部分:左边加 后,以 为起点继续拆分,有 种结果
2.3 边界条件
。因为 ,求和部分为空,只有 本身。
2.4 用前缀和优化
如果对每个 都从 累加到 ,时间复杂度 , 可以过,但可以做得更好。
定义前缀和:
那么递推式变为:
对每个 只需 时间,整体 ,非常高效。
2.5 手动推导前几项
| 1 | 0 | 1 | |
| 2 | 1 | 3 | |
| 3 | 1 | 5 | |
| 4 | 2 | 9 | |
| 5 | 2 | 13 | |
| 6 | 3 | 19 | |
| 7 | 3 | 25 | |
| 8 | 4 | 35 |
三、参考代码
3.1 递推写法(,推荐)
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
unsigned long long ans[N], pre[N];
int main() {
int n;
cin >> n;
ans[1] = 1;
pre[1] = 1;
for (int i = 2; i <= n; i++) {
ans[i] = 1 + pre[i / 2]; // i/2 自动向下取整
pre[i] = pre[i - 1] + ans[i]; // 维护前缀和
}
cout << ans[n] << endl;
return 0;
}为什么是
i / 2? C++ 中整数除法自动向下取整,i / 2等价于 。
3.2 递归写法(,自顶向下)
将递推式直接翻译成递归,配合记忆化:
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N];
long long dfs(int x){
// 递归边界 至少可以保留自己行程一个数字
if (x == 1) return 1;
if (a[x] != 0) return a[x];
int res = 1;// 答案,默认包括自己
// 枚举x左侧放数字的所有可能性:从1开始到 x/2
for(int i = 1; i <= x / 2; i++){
res += dfs(i); // 每个数字都拓展出 x/2个数字(可能性)
}
a[x] = res;
return a[x];
}
int main(){
int n;
cin >> n;
cout << dfs(n) << endl;
return 0;
}注意:递归写法的
for循环累加导致每个状态 ,总复杂度 。对 能过,但不如递推 + 前缀和优雅。若想收敛到 ,可以在dfs中先递归算出所有更小值再填表。
3.3 写法对比
| 递推 + 前缀和 | 递归 + 记忆化 | |
|---|---|---|
| 方向 | 自底向上 | 自顶向下 |
| 时间复杂度 | (带循环累加) | |
| 空间复杂度 | ||
| 思维难度 | 需要想到前缀和 | 公式直译,容易想到 |
四、复杂度分析
| 写法 | 时间 | 空间 |
|---|---|---|
| 递推 + 前缀和 | ||
| 递归 + 记忆化 |
- 递推版:每个 只做两次数组访问, 几乎瞬间完成。
- 递归版:每个状态要循环 次累加子问题,最坏约 万次操作,依然极快。
两种写法都对 绰绰有余。
五、知识扩展
5.1 这个数列叫什么?
本题的答案数列在 OEIS 上的编号是 A000123,也叫 "number of binary partitions of n"。前几项:
可以发现一个规律:相邻两项中,第奇数项和第偶数项的值往往相等(因为 对 和 相同)。
5.2 跟 1303 的联系
上一题「集合的划分」用递推公式 求解,本题同样用递推。两题共同点:
- 都从"最后一步"或"最先一步"入手拆分子问题
- 都用一个递推式表达大问题和子问题的关系
- 都能用记忆化递归或递推填表实现
区别在于上一题是二维递推,本题是一维递推;上题的递推不能直接优化成 ,本题可以通过前缀和做到 。
六、易错点
- 只输出 ,不要输出每个数。题目只要求输出个数,样例中列出的数是帮助理解的。
- 答案可能很大: 时答案远超过
int范围,必须用unsigned long long(或long long)。 - 循环边界写错: 从 到 ,不是 或别的范围。
- 忘记 本身:递推式中 代表"不做任何处理"的 自身,容易漏掉。
- 递归版效率陷阱:如果用纯递归(不记忆化),每个状态重复计算指数次, 就跑不动了。
