DP最小加法表达式
2016-07-13 本文已影响0人
Yanring_
题：有一个由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)
