題：有一個(gè)由1..9組成的數(shù)字串.問如果將m個(gè)加號插入到這個(gè)數(shù)字串中,在各種可能形成的表達(dá)式中，值最小的那個(gè)表達(dá)式的值是多少

狀態(tài)轉(zhuǎn)移：

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個(gè)數(shù)字到第j個(gè)數(shù)字所組成的數(shù)。數(shù)字編號從1開始算。

V(m,n) 表示在n個(gè)數(shù)字中插m個(gè)加號組成的最小數(shù)

此操作復(fù)雜度是O(j-i+1)

總時(shí)間復(fù)雜度： O(mn2)