# P1028 calculation of number (recursive & recursive)

2021-08-10 08:03:50

## P1028 The calculation of numbers （ recursive & Recurrence ）

Subject portal

Ideas ： set up a[i] by n=i When the number of programs . Know when i There is a scheme for not operating , then i You can add... To the left of the 1,2,…… i / 2, Then it is transformed into solving a[1],a[2],……a[i/2] Number of alternatives . This is obviously a recursive process , Because each scheme is obtained by prefix and , So we can use an array to hold prefixes and . The recursive formula ：a[ i ]=a[i-1]+(a[ i/2]+1)

Recursive writing ：

``````#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.
```

Recursive writing ：

``````#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.
```

https://chowdera.com/2021/08/20210810080205505r.html