上期停局，我們講解了樹形DP，通過搜索和DP相結(jié)合來解決問題∠愀現(xiàn)在董栽，我們將要擺脫搜索的束縛，真正探索動(dòng)態(tài)規(guī)劃的世界企孩。
今天锭碳，我來向大家講解一下區(qū)間動(dòng)規(guī)的問題模型和解決方法。
首先勿璃，顧名思義擒抛，區(qū)間動(dòng)規(guī)所要解決的問題是在一個(gè)序列上的推汽，每一個(gè)區(qū)間都是一個(gè)子問題，這些子問題最后一同構(gòu)成最終的問題歧沪。
按照套路歹撒，我們應(yīng)該先解決子問題，再解決父問題诊胞。那顯然應(yīng)該按區(qū)間的大小從小到大進(jìn)行處理暖夭。顯然，只有一個(gè)元素的時(shí)候撵孤，應(yīng)該是很容易得到答案的迈着。
接下來，我通過幾道例題加深大家對區(qū)間動(dòng)規(guī)的理解（例題來源洛谷邪码，侵刪）裕菠。
洛谷P1880
這道題是區(qū)間動(dòng)規(guī)的經(jīng)典題目。
閱讀題目霞扬，我們發(fā)現(xiàn)所有石子排成一列（問題在一個(gè)序列上）糕韧，每次合并兩對石子（區(qū)間子問題），所以顯然是一個(gè)區(qū)間動(dòng)規(guī)的問題喻圃。
那么怎么解決呢萤彩？
如果一段區(qū)間要合并，那么肯定是先將這段區(qū)間的兩個(gè)子區(qū)間合并成兩堆斧拍，再將這兩堆合并雀扶。一個(gè)問題是不是就轉(zhuǎn)換成兩個(gè)子問題了呢？
我們可以定義f[i][j]表示把第i個(gè)石子到第j個(gè)石子合并成一堆可以得到的最大價(jià)值肆汹，轉(zhuǎn)移方程很容易能得到：
最小值同理愚墓，自己試一試吧。
洛谷P3205
這是一道很有意思的題目【笑】昂勉。
這道題有兩個(gè)序列浪册，分別是初始序列和最終序列，那么我們要拿哪一個(gè)來DP呢岗照？
考慮初始序列村象，這題需要我們統(tǒng)計(jì)初始序列的方案樹，那么初始序列子區(qū)間的狀態(tài)不能用兩個(gè)端點(diǎn)來表示攒至，還需要其他的數(shù)據(jù)還記錄子區(qū)間厚者。如果狀態(tài)太多，顯然時(shí)間上是不可接受的迫吐，所以用初始序列來DP行不通库菲。
如果用最終序列來DP可行嗎？
我們發(fā)現(xiàn)最終序列是一個(gè)固定志膀，而且根據(jù)題意熙宇，隊(duì)形的排出是從一個(gè)元素逐漸拓展成最終序列的過程鳖擒。我們通過兩個(gè)端點(diǎn)和當(dāng)前序列最后進(jìn)入的人排在最左邊還是最右邊，就能表示出一個(gè)區(qū)間的信息（因?yàn)閰^(qū)間內(nèi)部奇颠，除了端點(diǎn)败去，其他數(shù)據(jù)都沒用）。所以用最終序列來DP是可行的烈拒。
我們定義f[i][j][0/1]表示i到j(luò)這個(gè)區(qū)間最后進(jìn)入的人在最左邊（最右邊）的方案數(shù)圆裕，轉(zhuǎn)移方程很容易得到：
總結(jié)，區(qū)間DP的關(guān)鍵點(diǎn)在于找到用于DP的區(qū)間荆几。這個(gè)區(qū)間應(yīng)該要容易表示吓妆，否則時(shí)間復(fù)雜度會過高。
【信息學(xué)競賽從入門到巔峰】吨铸，一個(gè)專注于分享OI/ACM常用算法及知識的公眾號行拢。
