動態(tài)規(guī)劃--字符串拆分

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

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

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

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