3028: 数的计数(Noip2001) 递推前缀和

解题思路:自然数的个数递推式：h[i] = h[1] + h[2] +...+ h[i/2]; s[i] 为h[i] 前缀和，所以h[i] = 1 + s[i/2]（扩展出的自然数包括i本身）; 计算前缀和s[i] =   s[i-1] + h[i];

注意事项:

参考代码:

#include<iostream>
#include<limits> 
using namespace std;
const int N = 1e5 + 10;
int h[N],s[N];

int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++){
		h[i] = 1 + s[i/2];
		s[i] = s[ i - 1 ] + h[i];
	}
	cout << h[n]; 
	return 0;
}