某種字符串處理語言允許程序員將一個字符串拆分為兩段。由于此操作需要復(fù)制字符串，因此要花費n個時間單位來將一個n個字符的字符串拆為兩段。假定一個程序員希望將一個字符串拆分為多段，拆分的順序會影響所花費的總時間。例如，假定這個程序員希望將一個20個字符的字符串在第2個，第8個以及第10個字符后進行拆分(字符由左至右，從1開始升序編號)。如果她按由左到右順序進行拆分，則第一次拆分花費20個時間單位，第二次拆掉分花費18個時間單位(在第8個字符處拆分3-20間的字符串)而第三次拆分花費12個時間單位，共花費50個時間單位。但如果她按由右至左的順序進行查分，第一次拆分花費12個時間單位，第二次拆分花費10個時間單位，而第三次拆分花費8個時間單位，共花費38個時間單位。還可以按其他順序，比如，她可以首先在第8個字符處進行拆分(時間20)，接著在左邊一段第2個字符處進行拆分(時間8)，最后在右邊一段第10個字符處進行拆分(時間12)，總時間為40.

設(shè)計算法，對給定的拆分位置，確定最小代價的拆分順序，更形式化地，給定一個n個字符的字符串S和一個保存m個拆分點的數(shù)組Lm,計算拆分的最小代價，以及最優(yōu)拆分序列。

設(shè)由Lm將S拆分成m+1個字符串，且每個字符串的長度按順序排列與tm+1中，令p=m+1。
設(shè)Mi,j(0≤i代表拆分后的子串i到子串j合并成的串在由Lm拆分時所需的最少時間單位(易知Mi,i=0,i∈{0,1,...,p?1})。

所以，
Mi,j=min{∑k=ijtk+Mi,q+Mq+1,j},q∈{i,i+1,..,j?1}