在n个数字中插入m个加号使表达式的值最小
num[i][j]:位置i到位置j的所表示的数字。

递推：
dp[m][n]表示在n个数字中插入m个加号所能形成的表达式最小值
边界条件：dp[0][i]=num[1][i]
递推公式：dp[i][j]=min(dp[i-1][k]+num[k+1][j])(i<=k<j) k:最后一个加号的位置，i<=k (i-1个加号至少要用i个数字) k<j(最远的位置j-1个数字的后面)

递归：
v(m, n)=min(v(m-1, i)+num(i+1, n)) (i=m.......n-1);
终止条件：if(m==0) return num[1][n];


递推：
#include<bits/stdc++.h>
using namespace std;

int a[50];
int num[50][50];
int dp[50][50];

int main()
{
    int n, m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        num[i][i]=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            num[i][j]=num[i][j-1]*10+a[j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        dp[0][i]=num[1][i];
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int s=(1<<31)-1;
            for(int k=i;k<j;k++)
            {
                s=min(s, dp[i-1][k]+num[k+1][j]);
            }
            dp[i][j]=s;
        }
    }
    cout<<dp[m][n]<<endl;

    return 0;
}

递归：
#include<bits/stdc++.h>
using namespace std;

int a[50];
int num[50][50];
int dfs[50][50]={{0}};

int v(int m, int n)
{
    if(m==0)
    {
        return num[1][n];
    }
    int s=(1<<31)-1;
    for(int i=m;i<=n-1;i++)
    {
        if(!dfs[m-1][i])
        {
            dfs[m-1][i]=v(m-1, i);
        }
        s=min(s, dfs[m-1][i]+num[i+1][n]);
    }
    return s;
}

int main()
{
    int n, m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        num[i][i]=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            num[i][j]=num[i][j-1]*10+a[j];
        }
    }
    cout<<v(m, n)<<endl;

    return 0;
}