7
6
这是一道简单思维题。
通过手算我们可以发现规律：（这里f[n]表示“n能用2的幂数相加的不同式子的种数”）
思路：
1.如果n是奇数，则f[n]=f[n-1]（一定要分个1出来，所以它的结果就等于偶数n-1的结果）
2.如果n是偶数，则考虑将它拆分为带1和不带1两种情况：
（1）带1：这种情况下种数为f[n-1]（也就是奇数n-1的结果）
（2）不带1：这种情况下种数为f[n/2]（很巧妙，分出来不带1的情况下肯定分出来的数每个都是偶数，这种情况下的种数可以等价于n/2的种数，因为把分出来的数都除以2不就是n/2分出来的数吗？）
综上：有递推公式：n为奇时，f[n]=f[n-1]；
n为偶时，f[n]=f[n-1]+f[n/2]；
此外，还要注意n==1时，直接初始化f[1]=1；
#include<cstdio> int f[1010]; int main(){ int n; scanf("%d",&n); f[1]=1; for(int i=2;i<=n;i++){ if(i%2!=0) f[i]=f[i-1]; else f[i]=f[i-1]+f[i/2]; } printf("%d\n",f[n]); return 0; }
#include<cstdio> #include<iostream> #include<algorithm> #include<map> #include <math.h> #include<bits/stdc++.h> using namespace std; typedef long long ll; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } const int INF=0x3f3f3f3f; const int maxn=5e5; int n; int a[maxn]; void inint(){ cin>>n; } int dfs(int x){ int p; if(x==2){ return 2; } if(x%2==0){ p=dfs(x/2)+dfs(x-1); } else if(x%2==1){ p=dfs(x-1); } return p; } int ans=0; int main(){ inint(); int z=dfs(n); cout<<z; }
原文：https://www.cnblogs.com/lipu123/p/12702026.html