最佳加法表达式





有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中,值最小的那个表达式的值是多少





解题思路



假定数字串长度是n,添完加号后,表达式的最后一个加号添加在第 i 个数字后面,那么整个表达式的最小值,就等于在前 i 个数字中插入 m – 1个加号所能形成的最小值,加上第 i + 1到第 n个数字所组成的数的值(i从1开始算)。







解题思路

设V(m,n)表示在n个数字中插入m个加号所能形成的表达式最小值,那么:

if m = 0,

V(m,n) = n个数字构成的整数

else if n < m + 1

V(m,n) = ∞

else

V(m,n) = Min{ V(m-1,i) + Num(i+1,n) } ( i = m ... n-1)

Num(i,j)表示从第i个数字到第j个数字所组成的数。数字编号从1开始算。此操

作复杂度是O(j-i+1)

总时间复杂度:O(mn 2 )

代码如下：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

int dp[100][200];

char str[500];

//dp[m][n]表示的是示在n个数字中插入m个加号所能形成的表达式最小值

int change(int x,int y)

{

    int t=0;

    for(int i = x ; i <= y ; i++)

    {

        t*=10;

        t+=(str[i]-'0');

    }

    return t;

}

int main()

{

    int n,m;

    while(scanf("%d%d",&m,&n)!=EOF)

    {

        scanf("%s",str+1);

        memset(dp,0,sizeof(dp));

        for(int i = 1 ; i <= m ; i++)

            for(int j = 1 ; j <= n ; j++)//初始化为无穷大

                dp[i][j]=99999999;

        for(int i = 1 ; i <= n ; i++)//如果m等于0,那么dp就等于从一加到n

            dp[0][i]=change(1,i);

        for(int i = 1 ; i <= m ; i++)//否则的话就剩第三种情况了

            for(int j = i ; j <= n ; j++)

                for(int k = i ; k <= j ; k++)

                    dp[i][j]=min(dp[i][j],dp[i-1][k]+change(k+1,j));//(i-1)~k,k~j(k肯定大于i-1)

        printf("%d\n",dp[m][n]);

    }

    return 0;

}