最佳加法表达式（DP）

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

思路：
添加完加号后，表达式的最后一个加号在第i个数字后面，那么整个表达式的最小值，则等于前i个数的m-1最佳加法表达式，加上i+1到n组成的数。//V(i,m-1)+num[i+1][n]

V（n,m）表示在n个数字中插入m个加号所能形成的表达式的最小值。

num[i][j]表示从第i个数到第j个数字所组成的数 

           Num[1][n];  n个数字构成的整数 //当m = 0
V（n,m） =  INF  //当m+1 > n
           Min{V（i,m-1） + Num(n, i+1)} (i = m ... n-1) //else

#include<iostream>  
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f;
int sz[1000]; 
int num[1000][1000];
int n,m;
int V(int n, int m) {
    if (m == 0) {
        return num[1][n];
    } else if (m+1 > n) {
        return INF; 
    } else { //m < n
        int ans = INF;
        for (int i = m; i <= n-1; i++) //最后一个数字后不放+号 
            ans = min(ans, V(i,m-1)+num[i+1][n]);

        return ans;
    }
}
int main() {
    while (cin >> n >> m) {
        for (int i = 1; i <= n; i++) 
            cin >> sz[i];

        //预处理，num[i][j]表示从第i个数到第j个数字所组成的数   
        for(int i = 1; i <= n; i++) {
            num[i][i] = sz[i];
            for (int j = i+1; j <= n; j++) {
                num[i][j] = num[i][j-1]*10 + sz[j];
            }           
        }
        cout << V(n,m) << endl; 
    }
    return 0;
}