这题为什么贴着递归的标签？？

如果用传统的递归来做肯定是超时的，所以要转变思路，传统递归是从上至下循环运算的，而我们需要从下至上运算

读取输入 n

初始化 dp 和 sum 数组（大小为 n+1）

设置基础情况：dp[1] = 1, sum[1] = 1

从 i=2 到 n 循环计算：

dp[i] = 1 + sum[i/2]

sum[i] = sum[i-1] + dp[i]

输出 dp[n]作为结果

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> dp(n + 1, 0);
	vector<int> sum(n + 1, 0);
	
	dp[1] = 1;
	sum[1] = 1;
	
	for (int i = 2; i <= n; i++)
	{
		dp[i] = sum[i / 2] + 1;
		sum[i] += sum[i - 1] + dp[i];
	}
	
	cout << dp[n] << endl;
	return 0;
}