数的计数（递归、递推、背包、规律、优化、复杂度）

题目描述

我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n（n≤1000），然后对此自然数按照如下方法进行处理：
不作任何处理；
在它的左边加上一个自然数，但该自然数不能超过原数的一半；
加上数后，继续按此规则进行处理，直到不能再加自然数为止。

输入输出格式

输入格式

自然数n

输出格式：

满足条件的数

输入输出样例

输入样例#1:

6

输出样例#1:

6

输入样例#2:

3

输出样例#2:

2

【数据范围】

（n≤1000）

输出解释

6     满足条件的数为  	6   
                  		16
                  		26
                 		126
                 		36
                 		136

2     满足条件的数为  	2   
                  		12

欧阳的解法1

#include<bits/stdc++.h>
using namespace std;
int k=0;
int ans;
void dfs(int m){
	int i;
	ans++;
	for(i=1;i<=m/2;i++)
		dfs(i);	
}
int main(){
	int n;
	cin>>n;
	dfs(n);	//n前面能加哪些数 
	cout<<ans;
	return 0;
} 

优化

#include<bits/stdc++.h>
using namespace std;
int count = 0;
int m[10000];
void dfs(int n){
	if(n==0)
		return;
	if(m[n]) return;
	m[n]++;
	for(int i = 1;i<=n/2;i++){
		dfs(i);
		m[n]+=m[i];
	}
}
int main(){
	int n;
	cin>>n;
	dfs(n);
	cout<<m[n];
	return 0;
} 

再优化o(n^2)

#include<iostream>
using namespace std;
int h[10001];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)   //按照递增顺序计算扩展出的自然数的个数
    {
        h[i] = 1;                        //扩展出的自然数包括i本身
        for (int j = 1; j <= i/2; j++)         
                                 //i左边分别加上1…自然数 按规则扩展出的自然数
          h[i] += h[j]; 
    }
    cout << h[n];
    return 0;
}

再优化o(n)

#include<iostream>
using namespace std;
int h[1001],s[1001];
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];                  //s是h的前缀累加和
    }
    cout << h[n];
    return 0;
}