一个十进制整数被叫做权势二进制，当他的十进制表示的时候只由0或1组成。例如0，1，101，110011都是权势二进制而2，12，900不是。
当给定一个n的时候，计算一下最少要多少个权势二进制相加才能得到n。
Input
单组测试数据。
第一行给出一个整数n (1<=n<=1,000,000)
Output
输出答案占一行。
Input示例
9
Output示例
9
思路：完全背包刚刚装满背包；
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
const int N=2e5+,M=1e6+,inf=1e9+,mod=1e9+;
const ll INF=1e18+;
int a[N];
int check(int x)
{
while(x)
{
if(x%!=&&x%!=)
return ;
x/=;
}
return ;
}
int dp[M];
int main()
{
int flag=;
for(int i=;i<=;i++)
if(check(i))
a[flag++]=i;
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
dp[i]=inf;
dp[]=;
for(int i=;i<flag;i++)
{
for(int t=a[i];t<=n;t++)
{
dp[t]=min(dp[t],dp[t-a[i]]+);
}
}
printf("%d\n",dp[n]);
return ;
}