DP最小加法表达式

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

状态转移：

if m = 0

V(m,n) = Num(1,m)

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开始算。

V(m,n) 表示在n个数字中插m个加号组成的最小数

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

总时间复杂度： O(mn2)