你好！这是这道题的 动态规划（递推） 版本答案。

相比于记忆化搜索的“从上往下”算，动态规划是“从下往上”算（先算 $f[1]$，再算 $f[2]$……一直推到 $f[n]$）。

这里我提供两个版本：

1. 普通递推版 ($O(N^2)$)：直接翻译题目公式，最好理解。
2. 优化递推版 ($O(N)$)：利用奇偶性质优化，推荐使用这个版本，代码最短且效率最高。

版本一：普通递推版（最直观）

思路： 根据题目定义，$f[i]$ 的方案数等于它本身（1种）加上左边能拼接的所有数（$1$ 到 $i/2$）的方案数之和。 公式：$f[i] = 1 + \sum_{j=1}^{i/2} f[j]$

#include <bits/stdc++.h>
using namespace std;

int f[1005]; // DP数组

int main(){
    int n;
    cin >> n;
    
    // 初始化
    f[1] = 1; 
    
    // 从小到大依次计算每个数的方案数
    for(int i = 2; i <= n; i++) {
        f[i] = 1; // 1 代表它本身不做处理这一种情况
        
        // 累加左边所有可能的数的方案数
        // 比如算 f[6]，就要加 f[1] + f[2] + f[3]
        for(int j = 1; j <= i/2; j++) {
            f[i] += f[j];
        }
    }
    
    cout << f[n] << endl;
    return 0;
}

版本二：优化递推版（$O(N)$，推荐！）

思路： 通过观察数据规律（或者利用前缀和思想推导），我们可以发现：

• 如果 $i$ 是奇数：它的一半取整后和 $i-1$ 的一半一样，所以方案数不变 $\to f[i] = f[i-1]$。
• 如果 $i$ 是偶数：它比 $i-1$ 多了一个可以拼接的数（即 $i/2$），所以方案数要加上这一项 $\to f[i] = f[i-1] + f[i/2]$。

这个逻辑比上面的双重循环要快得多。

#include <bits/stdc++.h>
using namespace std;

int f[1005];

int main(){
    int n;
    cin >> n;
    
    // 初始化
    f[0] = 1; // 为了配合递推逻辑，通常设 f[0]=1 或者直接从 f[1] 开始特殊处理
    f[1] = 1; 
    
    // 一层循环，利用奇偶性质递推
    for(int i = 2; i <= n; i++){
        if(i % 2 == 1){
            // 奇数：方案数等于前一个数
            f[i] = f[i-1];
        } else {
            // 偶数：方案数等于前一个数 + 它可以拼接的那一半数的方案数
            f[i] = f[i-1] + f[i/2];
        }
    }
    
    cout << f[n] << endl;
    return 0;
}

为什么推荐版本二？

虽然版本一更容易理解，但在 OI 竞赛中，如果 $N$ 的范围变大（例如到 $10^5$），版本一的 $O(N^2)$ 就会超时，而版本二的 $O(N)$ 依然能过。养成寻找递推规律的习惯是非常重要的。

你好！我是你的 OI 教练。

这就为你提供这道题的记忆化搜索版本代码。

核心思路回顾

1. 公式：$f(n) = 1 + \sum_{i=1}^{\lfloor n/2 \rfloor} f(i)$。
2. 痛点：普通递归会重复计算（比如算 $f(6)$ 要用到 $f(3)$，算 $f(8)$ 也要用到 $f(3)$，导致 $f(3)$ 被反复计算）。
3. 药方：用一个数组 h[]（备忘录）把算过的结果存下来。每次计算前先查表，算完后存表。

C++ 代码实现

#include <bits/stdc++.h>
using namespace std;

// 记忆化数组
// h[i] 用来存储数字 i 的方案数
// 全局变量默认初始化为 0，我们用 0 表示“还没算过”
int h[1005]; 

int dfs(int n) {
    // 【步骤1：查表】
    // 如果 h[n] 不等于 0，说明之前已经算过了，直接返回答案！
    // 这就是“记忆化”的核心，能避免重复计算
    if (h[n] != 0) {
        return h[n];
    }

    // 【步骤2：计算】
    // 如果没算过，就老老实实算一遍
    int ans = 1; // ans 初始为 1，因为数字 n 本身不做任何处理也是一种方案
    
    // 递归累加：左边可以加的数是 1 到 n/2
    for (int i = 1; i <= n / 2; i++) {
        ans += dfs(i);
    }

    // 【步骤3：存表】
    // 算出来了，赶紧记到本子上（h数组），方便下次用
    h[n] = ans;
    
    return ans;
}

int main() {
    int n;
    cin >> n;
    
    // 直接调用 dfs
    cout << dfs(n) << endl;
    
    return 0;
}

代码解析

• h[1005]：这就是备忘录。因为 $n \le 1000$，开 1005 足够了。
• if (h[n] != 0)：这是记忆化搜索的灵魂语句。就像你做作业，遇到一道题先看看参考书上有没有答案，有就直接抄，没有再自己算。
• h[n] = ans：算出答案后，一定要保存，否则下次还得重算。

这个版本的时间复杂度从指数级直接降到了 $O(N^2)$ 级别，对于 $N=1000$ 的数据是秒过的。

你好！我是你的 OI 教练。

这道题（P1028 [NOIP 2001 普及组] 数的计算）是一道非常经典的递推/动态规划入门题目。它考察的是你如何把一个看似复杂的递归过程转化为高效的递推公式。

下面是解题思路提示：

1. 读题与拆解：递归的本质

题目说“在左边加上一个自然数，不能超过原数的一半”。 举个例子，假设 $n=6$：

• 首先，6 本身算一种情况。
• 左边可以加什么数？可以是 $1, 2, 3$（因为都 $\le 6/2$）。
  • 如果加 1，变成 16。接下来看 1 能不能再变？（1的一半是0.5，没法加自然数了，停止）。
  • 如果加 2，变成 26。接下来看 2 能不能再变？（2的一半是1，可以加1变成126）。
  • 如果加 3，变成 36。接下来看 3 能不能再变？（3的一半是1.5，可以加1变成136）。

核心发现： 对于数字 $n$，它的方案数 $f(n)$ 等于 1（它自己） 加上 所有可能的“左边数”的方案数之和。 数学公式表示：

也就是：$f(n) = 1 + f(1) + f(2) + \dots + f(n/2)$

2. 最大的坑：直接递归会超时

如果你直接写一个递归函数按照上面的公式去算：

int count(int n) {
    int ans = 1;
    for(int i = 1; i <= n/2; i++)
        ans += count(i);
    return ans;
}

当 $n=1000$ 时，这个程序会运行非常非常久（指数级复杂度），因为很多中间结果（比如 $f(3), f(4)$）被重复计算了无数次。千万不要直接裸写递归。

3. 优化思路 A：记忆化搜索

既然重复计算了，那我们就用一个数组 h[] 把算过的结果存起来。

• 每次进入函数先检查 h[n] 是不是已经算过了。
• 如果算过直接返回。
• 没算过再算，算完存进 h[n]。

4. 优化思路 B：递推（动态规划 DP）—— 推荐！

我们可以倒过来想，从小到大把所有数的方案数都算出来存到数组 f[] 里。

• $f[1] = 1$
• $f[2] = 1 + f[1]$
• $f[3] = 1 + f[1]$
• $f[4] = 1 + f[1] + f[2]$
• ...
• 一直算到 $f[n]$。

这样只需要两层循环，运算次数大约是 $N^2$ 级别，对于 $N=1000$ 来说轻轻松松。

5. 进阶规律（O(N) 极速解法）

如果你仔细观察上面的递推数组，你会发现一个惊人的规律：

• 当 $n$ 是奇数时（比如 3）：$f[3] = f[2]$。
  • 原理：3 的一半取整是 1，2 的一半也是 1。它们的求和范围是一样的。
• 当 $n$ 是偶数时（比如 4）：$f[4] = f[3] + f[2]$。
  • 原理：4 的一半是 2，比 3 的一半多了一个“2”。所以多加了一项 $f(2)$。

最终递推式：

f[i] = f[i-1];           // i 是奇数
f[i] = f[i-1] + f[i/2];  // i 是偶数

用这个公式，一层循环就能解决问题！

总结代码框架

建议使用 优化思路 B 或 进阶规律 来编写代码。

定义数组 f[1005];
初始化 f[1] = 1;

循环 i 从 2 到 n:
    如果是思路B:
        f[i] = 1;
        循环 j 从 1 到 i/2:
            f[i] += f[j];
    
    如果是进阶规律:
        // 根据奇偶性直接计算 f[i]

输出 f[n];

加油！试着写出代码并提交吧。

C :

#include <stdio.h>
int fan(int n)
{int h=1,i;
 i=n/2;
	if(n==1)
  return 1;
else 
  for(;i>=1;i--)
	  h=h+fan(i);
	return h;}
 
int main()
{int n;
scanf("%d",&n);
printf("%d",fan(n));
return 0;
}

C++ :

#include <iostream>
using namespace std;
long long f[100001];
long long comp (long long n){
     long long s=1,i;
     for (i=1;i<=n/2;i++){
         if (!f[i])
            f[i]=comp (i);
         s+=f[i];
     }
     return s;
}
int main ()
{
long long n;
cin>>n;
cout<<comp (n);
return 0;
}

Pascal :

var n,i,j:longint;
    p:array[0..10000]of longint;
begin
 readln(n);
 p[1]:=1;
 for i:=2 to n do
  begin
   for j:=1 to i div 2 do
    p[i]:=p[i]+p[j];
   inc(p[i]);
  end;
 writeln(p[n]);
end.

Java :

import java.util.*;
public class Main{
  public static int cnt = 1;
  public static void main(String[] args) {
  long startTime = System.currentTimeMillis();
    Scanner cin = new Scanner(System.in);
    int n = cin.nextInt();
    recursion(n);

    System.out.println(cnt);
    long endTime = System.currentTimeMillis();
    // System.out.println(endTime-startTime);
  }

  public static void recursion(int n){
    for(int i = 1; i <= n/2; i ++){
      cnt++;
      recursion(i);
    }
  }
}