1.什么樣的問(wèn)題適合動(dòng)態(tài)規(guī)劃戚炫？
基本上有兩個(gè)特征：（a）是一個(gè)最優(yōu)化問(wèn)題（optimal）稠肘；（b）有個(gè)最優(yōu)子結(jié)構(gòu)（substructure）猖毫，狀態(tài)轉(zhuǎn)移只依賴(lài)最近的幾項(xiàng)保礼，這點(diǎn)類(lèi)似遞歸吃度。
具體例子參見(jiàn)：LCS（longest common substring）甩挫，背包問(wèn)題，最少硬幣等等椿每。
2.和遞歸有什么不同伊者？
遞歸只是一種寫(xiě)法。
最大的不同是有重疊的子問(wèn)題间护。遞歸算法一般來(lái)說(shuō)是可以解決動(dòng)態(tài)規(guī)劃問(wèn)題亦渗，但是復(fù)雜度相比窮舉幾乎沒(méi)有改善，這時(shí)兑牡，如果畫(huà)出解決流程的決策樹(shù)央碟，就會(huì)發(fā)現(xiàn)有很多重疊的子問(wèn)題。
這點(diǎn)帶來(lái)的好處就是可以大幅度減少運(yùn)算均函。比如最簡(jiǎn)單的memo法（判斷子問(wèn)題算過(guò)就不再算）亿虽，還有直接正序計(jì)算。這里的正序計(jì)算就是一般意義上的動(dòng)態(tài)規(guī)劃法苞也。
3.例題
a.最長(zhǎng)的升序的子序列（子序列和子串的區(qū)別是不用連續(xù)）：
技巧是建立狀態(tài)轉(zhuǎn)移：以每個(gè)序列的結(jié)尾的數(shù)作為下標(biāo)洛勉，以長(zhǎng)度作為狀態(tài)值，這樣新來(lái)一個(gè)就好判斷了如迟。
b.區(qū)間和最大：
技巧是狀態(tài)轉(zhuǎn)移：下標(biāo)是數(shù)列的下標(biāo)收毫，記錄的是以當(dāng)前下標(biāo)指向的數(shù)結(jié)尾的和最大的區(qū)間（注意，沒(méi)有定區(qū)間起點(diǎn)殷勘，這個(gè)可以最后再找最大的此再，定了區(qū)間的終點(diǎn)，這樣就容易遞歸了）
c.長(zhǎng)度為n的01組成的字符串玲销，不含連續(xù)3個(gè)0输拇。問(wèn)：有幾種？
dp(i,0)以0結(jié)尾的長(zhǎng)度為i的字符串有幾種贤斜；dp(i,1)以1結(jié)尾的....策吠；
然后枚舉i-1和i-2的情況，如果同時(shí)為0瘩绒，那么i位置只能為0猴抹。所以，
dp(i,0)=dp(i-1,0) + dp(i-1,1) - dp(i-2,0)
dp(i,1)=dp(i-1,0) + dp(i-1,1)
結(jié)果是dp(n,0)+dp(n,1)
d.p次入棧锁荔，q次出棧的可能的順序有幾種蟀给？
也是枚舉末尾狀態(tài)：末尾是出棧/入棧，所以，f(p,q)=f(p-1,q)+f(p,q-1)
e.n堆石子坤溃，構(gòu)成一個(gè)vector拍霜，每次合并相鄰的兩堆，消耗是這兩堆石子數(shù)目之和薪介，問(wèn)怎么合并消耗最小，最小是多少越驻？
dp(i,j)表示從i~j合并的最小消耗汁政，那么求dp(i,j)可以枚舉最后一步是合并的哪兩個(gè)部分。這個(gè)題沒(méi)有特別巧妙的方法缀旁，復(fù)雜度為O(n^3)
進(jìn)階1：n堆石子记劈，每次合并任意兩堆，最小消耗是多少并巍？
找最小的兩堆合并目木，完了把這堆加入，再找最小的兩堆合并懊渡，一直下去
進(jìn)階2：n堆石子刽射，每次合并堆的數(shù)目必須小于等于m，最小消耗是多少剃执？
可以用m-叉樹(shù)來(lái)說(shuō)明這個(gè)問(wèn)題誓禁。其邏輯見(jiàn)下一題（Huffman編碼）。假設(shè)已經(jīng)說(shuō)明了我們只要第一次合并是小于m的肾档，其他都是m次摹恰，那么根據(jù)n，可以求出m來(lái)（n-(x-1)-k(m-1)=1）怒见，這樣就完全確定了俗慈。為什么要小于m只能是在第一次：不然可以把葉子節(jié)點(diǎn)移到上面去，消耗是減小的遣耍。
f.Huffman編碼：根據(jù)每個(gè)字母出現(xiàn)的頻率闺阱，確定其Huffman編碼（01組成，任何一個(gè)字母的編碼不能是其他編碼的前綴）
這里的邏輯也是一直找最小的堆合并配阵。用樹(shù)來(lái)模擬這個(gè)過(guò)程：從葉子節(jié)點(diǎn)開(kāi)始建馏颂，找頻率最低的兩個(gè)，然后
