n给一个整数n，要你找一个值为n的表达式，这个表达式只有1 + * ( ) 够成。并且1不能连续，比如11+1就不合法。
n输入n,(1<=n<=10000)
n输出最少需要多少个1才能构成表达式。
n样例：n=2=1+1 ans=2
n n=10=(1+1)*(1+1+1+1+1) ans=7
【可以看出，当一个数 i 是素数的时候，这个数只能由 i 个1组成；但是当它不是素数的时候，可以把这个数拆分成它的因子的乘机的形式。】
让dp[i]表示最少数量的1能够表示i。
add: dp[i]=dp[j]+dp[i-j] 0<j<i
multiply: dp[i]=dp[j]+dp[i/j] 0<j<i, i%j=0（有因子）
【code】
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int dp[1000];
void dps()
{
int i,j;
dp[0]=0;
dp[1] = 1;
for(i = 2;i<1000;i++)
{
dp[i] = i;
for( j = 1;j<i;j++)
{
dp[i] = min(dp[i],dp[j]+dp[i-j]); if(i%j==0)
dp[i] = min(dp[i],dp[j]+dp[i/j]);
}
}
}
int main()
{
int n;
dps();
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",dp[n]);
}
return 0;
}
转载于:https://www.cnblogs.com/plxx/p/3232383.html
相关资源：数据结构—成绩单生成器
