题目
分析
这道题目不难。题目的表述虽然有点绕，但已经给出了明显的“递归”思路：
- 如果初始是
6，那么一次操作后可以得到6 3，6 2，6 1。 - 第二次操作，可以从
6 3得到6 3 1，从6 2得到`6 2 1。 - 加上初始的
6，一共有6个数列。
所以，核心就是：
从当前最后一个数字（last）开始从1到last/2，递归计算这些数字分别能进行上述的操作。
当然，这里有重复的计算，所以我们还能用记忆化的方式来加快计算。
答案
思考
这题用来作为递入门是不错的选择。当然，我们也可以跳开递归，而直接使用动态规划的方式。代码如下：
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
// dp[i]表示以i为最后一个元素的合法数列的数量
vector<long long> dp(n + 1, 0);
// 自底向上填充dp表
for (int i = 1; i <= n; i++) {
// 初始化为1（表示只有i这一个元素的数列）
dp[i] = 1;
// 尝试在数列末尾添加1到i/2的任意整数
for (int j = 1; j <= i / 2; j++) {
dp[i] += dp[j];
}
}
cout << dp[n] << endl;
return 0;
}