问题描述

有一个由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²)。

程序实现

#include<iostream>
#include<string>
#include<cstdlib>
#include<cstdio>
using namespace std;

const int MAXN = 1001;
const int MAXM = 1001;
const int INFINITE = 1000000;
int f[MAXN][MAXM];

int main()
{

    string str;
    cin >> str;
    int m;
    cin >> m;
    int n = str.length();
    str = "0" + str;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= m; j++)
            f[i][j] = INFINITE;
    for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j <= m; j++)
                {
                    if(j == 0)
                        {
                            f[i][j] = atoi(str.substr(1, i).c_str());
                            cout << "i=" << i << "," << "j=" << j << "," << f[i][j] << endl;
                            continue;
                        }
                    if(i == j + 1)
                        {
                            int tmp = 0;
                            for(int s = 1; s <= i; s++)
                                tmp += str[s] - '0';
                            f[i][j] = tmp;
                            cout << "i=" << i << "," << "j=" << j  << "," << f[i][j] << endl;
                        }
                    if(i > j + 1)
                        {
                            for(int k = j; k <= i - 1; k++)
                                {
                                    int num = atoi(str.substr(k + 1, i - k).c_str());
                                    f[i][j] = min(f[i][j], f[k][j - 1] + num);
                                    cout << "i=" << i << "," << "j=" << j << "," << "num=" << num << "," << f[i][j] << endl;
                                }

                        }



                }
        }

    if(f[n][m] < INFINITE) cout << f[n][m] << endl;
    else cout << "None!" << endl;

}

运行结果