P1028 [NOIP 2001 普及组] 数的计算——题解

解题思路

令 f[i] 表示以 $i$ 开头的合法数列数。只取一个数时有 1 种；若继续添加，下一项可以是 $1$ 到 $\lfloor i/2 floor$，选择 $j$ 后后续方案数为 f[j]。因此 f[i]=1+sum(f[j])。按 $i$ 从小到大递推。

复杂度分析

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
long long f[1005];
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){f[i]=1;for(int j=1;j<=i/2;j++)f[i]+=f[j];}
    cout<<f[n]<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; long long f[1005]; int main(){ int n;cin>>n; for(int i=1;i<=n;i++){f[i]=1;for(int j=1;j<=i/2;j++)f[i]+=f[j];} cout<<f[n]<<'\n';return 0; }