ones

/*n给一个整数n，要你找一个值为n的表达式，这个表达式只有1 + * ( )够成。并且1不能连续，比如11+1就不合法。n输入n,(1<=n<=10000)n输出最少需要多少个1才能构成表达式。n样例：n=2=1+1                      ans=2       n=10=(1+1)*(1+1+1+1+1)       ans=7dp[i]表示最少数量的1能够表示i，分为两种情况，加法和乘法，状态转移方程式为add:           dp[ i ] = dp[ j ] + dp[ i - j ]      0<j<imultiply:    dp[ i ] = dp[ j ] + dp[ i / j ]      0<j<i, i%j=0*/#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>using namespace  std;const int maxn=10005;int n,dp[maxn];void work(){     dp[0]=0,dp[1]=1;     for(int i=2;i<=10005;i++)     {         dp[i]=i;         for(int j=1;j<i;j++)         {             dp[i]=min(dp[i],dp[i-j]+dp[j]);             if(i%j==0)             dp[i]=min(dp[i],dp[j]+dp[i/j]);         }     }}int main(){    work();    while(scanf("%d",&n)!=EOF)    printf("%d\n",dp[n]);    return 0;}