半数集问题_牛客博客

问题描述：
给定1个自然数n，求由n产生的半集数set(n)中的数：n∈set(n)，在n左边加一个不超过最近添加的数一半的数，不断这样处理，直至不能添加自然数为止。
如：输入n=6 得到set(6)={6,16,26,126,36,136,236}，共6个元素。

思路：这题比较简单，因为左边不能超过n/2，所以直接枚举每个数的[1,n/2]，然后统计一下就行了。枚举到1的时候结束枚举，因为1再/2就 = 0了，那整个数也就变成0了，显然不满足题意。
代码：

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

int ans = 1;
void dfs(int n){
	if(n == 1)return ;//递归出口，即1无法再/2
	for(int i=1;i<=n/2;i++){//枚举[1,n/2]
		dfs(i);//递归枚举每个数
		ans++;//枚举完一个计数一次
	}
}
int main(){
	int n;cin>>n;
	dfs(n);
	cout<<ans<<endl;
}

用数组存中间结果的记忆化搜索

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

const int maxn = 1e4 + 10;
int ans = 1;
int t[maxn];
int dfs(int n){
	if(t[n] > 0)return t[n];
	int s = 1;
	for(int i=1;i<=n/2;i++){
		s +=dfs(i);
	}
	return t[n] = s;
}
int main(){
	int n;cin>>n;
	dfs(n);
	cout<<t[n]<<endl;
}

dp做法：
dp[i] :数字i产生的半集数数量
转移方程： $d p [i] = 1 + <munderover> \sum i = 1 i = n / 2 </munderover> d p [i]$
代码：

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

const int maxn = 1e3 + 10;
int dp[maxn];
int main(){
	int n;cin>>n;
	for(int i = 1; i <= maxn; i++)dp[i] = 1;
	dp[1] = 1;
	for(int i = 2; i <= n; i++){
		for(int j = 1; j <= i/2; j++){
			dp[i] += dp[j];
		}
	}
	cout<<dp[n]<<endl;
}