P1028 数的计算 （递归&递推）

题目传送门

思路：设a[i]为n=i时的方案数。可知当 i 不进行操作有一种方案，然后 i的左边可以加1，2，…… i / 2,然后又转化为求解a[1],a[2],……a[i/2]的方案数。这显然是一个递推过程，由于每个方案都是由前缀和得到，所以我们可以用一个数组保存前缀和。递推公式：a[ i ]=a[i-1]+(a[ i/2]+1)

递推写法：

#include<bits/stdc++.h>
using namespace std;
int b[1005],n;
int main(){
	cin>>n;
	for(int i=1;i<=n/2;i++)
	b[i]=b[i-1]+(b[i/2]+1); 
	cout<<b[n/2]+1<<endl;
	return 0;
}

递归写法：

#include<bits/stdc++.h>
using namespace std;
int sum[1005],n;
int dfs(int x){
	if(x==1) return sum[x]=1;
	if(sum[x]) return sum[x];
	int ans=0;
	for(int i=1;i*2<=x;i++)
		 ans+=dfs(i);
	return sum[x]=ans+1;
} 
int main(){
	cin>>n;
	dfs(n);
	cout<<sum[n]<<endl;
	return 0;
}