数字拆分成4段，怎样使得4段的乘积最小

题目是：给出一个数字（10,000～100,000,000），把这个数字拆分成4段，怎样使得4段的乘积最小。比如12345拆分成1*2*3*45=270, 10000=1*00*0*0=0。

题目分析：

这道题很明显能用动态规划（dp）来求解，用dp(i,j)表示：以指向第j个位置字的符结束的字符串还需要分为i份所得到的最小乘积，那么题目中的12345的正解就是dp(4,5)表示以第5个字符（‘5’）结束的字符串分成4份所得到的最小乘积。

num(i,j)表示字符串中从第i个字符到第j个字符组成的字符串的值，如12345中，num(2,4)=234

My Code:

[cpp]  view plain  copy #include <iostream>   #include <string>   using namespace std;      int dp[5][20];      int num(const string &str,int b,int e)   {       b--;       e--;       int res=0;       while(b<=e)       {           res=(str[b++]-'0')+res*10;       }       return res;   }      int main()   {       for(int i=0;i<5;i++)           for(int j=0;j<20;j++)               dp[i][j]=1;          string str;       cin>>str;       int len=str.size();          for(int i=1;i<=4;i++)           for(int j=i;j<=len;j++)           {               if(i==j)               {                   int res=1;                   for(int t=0;t<j;t++)                   {                       res*=(str[t]-'0');                   }                   dp[i][j]=res;               }               else if(i!=1)               {                   int min=0x7FFFFFFF;                   for(int k=i-1;k<j;k++)                   {                       int temp=dp[i-1][k]*num(str,k+1,j);                       if(temp<min)                       min=temp;                   }                   dp[i][j]=min;               }               else if(i==1)               {                   dp[i][j]=num(str,1,j);               }              }       cout<<dp[4][len]<<endl;       return 0;   }