有一个数字1，2，3，….，9组成的数字串（长度不超过200），问如何将M（M<=20）个加号插到这个数字串中，使得形成的算数表达式的值最小，请编写一个算法解决这个问题。 注意：加号不可加在字符串的最前面或者最后面，也不应该有两个或两个以上的加号相邻。M保证小于数字串的长度

这是一个经典的动态规划问题，可以使用动态规划算法来解决。

首先，我们定义一个二维数组 $dp[i][j]$ 表示将前 $i$ 个数字分成 $j$ 段所得到的最小值。其中 $i$ 的取值范围是从 $1$ 到 $9$，$j$ 的取值范围是从 $2$ 到 $M+1$。

接下来，我们考虑如何填充这个数组。首先，对于 $dp[1][j]$（$2\leq j\leq M+1$），由于只有一个数字，无论分成几段，答案都是这个数字本身。因此，$dp[1][j]$ 的初始值为 $1$ 到 $M+1$。

然后，对于 $dp[i][j]$（$2\leq i\leq 9$，$2\leq j\leq M+1$），我们可以考虑将前 $i$ 个数字划分成两部分：第一部分是前 $k$ 个数字，第二部分是剩下的 $i-k$ 个数字。这样，就可以将 $dp[i][j]$ 的计算转化为 $dp[k][j-1]$ 和第一部分的和的最小值之和。

具体地，我们可以枚举前 $k$ 个数字的长度 $l$，将前 $l$ 个数字作为第一部分，后面的数字作为第二部分。那么，第一部分的和就是 $dp[l][j-1]$，第二部分的和就是 $\sum_{m=l+1}^i a_m$，其中 $a_m$ 表示第 $m$ 个数字。因此，$dp[i][j]$ 的计算公式为：

$$dp[i][j]=\min\limits_{1\leq l\leq i-1}(dp[l][j-1]+\sum_{m=l+1}^i a_m)$$

最终，$dp[9][M+1]$ 就是将数字串分成 $M+1$ 段所得到的最小值。

时间复杂度为 $O(9M^2)$。