5.数字拆分成4段，怎样使得4段的乘积最小【dp】

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

解题分析稍后给出。。。

My Code:

#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;}