当前位置:网站首页>P1028 数的计算 (递归&递推)

P1028 数的计算 (递归&递推)

2021-08-10 08:02:31 wx6110fa547fd20

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;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.

递归写法:

#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;
}

      
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15326986/3328306

随机推荐