之前簡(jiǎn)單介紹了動(dòng)態(tài)規(guī)劃的概念和解題步驟陋桂，但是學(xué)習(xí)中感覺動(dòng)態(tài)規(guī)劃的應(yīng)用范圍太靈活了，這里就挑一些常見的題目多練習(xí)一下。
1杨箭、最長(zhǎng)公共子序列（字符串相關(guān)）
給出兩個(gè)字符串，找到最長(zhǎng)公共子序列(LCS)储狭，返回LCS的長(zhǎng)度互婿。例如：
例如：給出"ABCD"和"EDCA"捣郊，這個(gè)LCS是 "A"(或 D或C)，返回1慈参；
給出"ABCD" 和 "EACB"呛牲，這個(gè)LCS是"AC"返回2。
思路：長(zhǎng)度為m的字符串a(chǎn)和長(zhǎng)度為n的字符串b驮配，他們的最長(zhǎng)公共子序列l(wèi)ongest[m][n]可通過m-1長(zhǎng)度的a和n-1長(zhǎng)度的b推得：當(dāng)a[m]等于b[n]的時(shí)候娘扩，longest[m][n] = longest[m-1][n-1] + 1；當(dāng)a[m]不等于b[n]時(shí)壮锻，longest[m][n]=max(longest[m-1][n], longest[m][n-1])琐旁。當(dāng)字符串a(chǎn)或者b為空字符串時(shí)，它與另一個(gè)字符串的最長(zhǎng)公共子序列必然是0猜绣。最后題目的解即為longest[strlen(a)][strlen(b)]灰殴。
代碼：
2、編輯距離（字符串相關(guān)）
給出兩個(gè)單詞word1和word2掰邢，計(jì)算出將word1 轉(zhuǎn)換為word2的最少操作次數(shù)牺陶。
你總共三種操作方法：插入一個(gè)字符、刪除一個(gè)字符尸变、替換一個(gè)字符义图。
例如：給出 work1="mart" 和 work2="karma"，返回 3召烂。
思路：對(duì)于長(zhǎng)度為m的字符串a(chǎn)和長(zhǎng)度為n的字符串b（m碱工、n都大于0），如果a[m]不等于b[n]奏夫，那么a變?yōu)閎的最小操作次數(shù)=min(a[m-1]變?yōu)閎[n]的最小操作次數(shù)+1怕篷，a[m]變?yōu)閎[n-1]的最小操作次數(shù)+1，a[m-1]變?yōu)閎[n-1]的最小操作次數(shù))酗昼；如果a[m]等于b[n]廊谓，那么a[m]變?yōu)閎[n]的最小操作次數(shù)=a[m-1]變?yōu)閎[n-1]的最小操作次數(shù)。
代碼：
3麻削、背包問題
給出n個(gè)物品的體積A[i]和其價(jià)值V[i]蒸痹，將他們裝入一個(gè)大小為m的背包，最多能裝入的總價(jià)值有多大呛哟？
例如：對(duì)于物品體積[2, 3, 5, 7]和對(duì)應(yīng)的價(jià)值[1, 5, 2, 4], 假設(shè)背包大小為10的話叠荠，最大能夠裝入的價(jià)值為9。
思路：當(dāng)空間為v時(shí)扫责，對(duì)于任意一個(gè)物品i榛鼎，如果i可以放入（v大于等于weight[i]），則此時(shí)v空間的價(jià)值f(v)等于f(v-weight[i]) + values[i]，因此通過遍歷全部物品可以找到在空間為v時(shí)所能得到的最大值者娱。
代碼：
4抡笼、區(qū)間問題（谷歌面試題）
有n個(gè)硬幣排成一條線，每一枚硬幣有不同的價(jià)值黄鳍。兩個(gè)參賽者輪流一從任意一邊取一枚硬幣推姻，直到?jīng)]有硬幣為止。計(jì)算拿到的硬幣總價(jià)值际起，價(jià)值最高的獲勝拾碌。請(qǐng)判定第一個(gè)玩家是輸還是贏？
例如：給定數(shù)組[3,2,2]街望，返回true；給定數(shù)組[1,20,15]弟跑，返回false灾前。
思路：對(duì)于給定的一個(gè)閉區(qū)間（i到j(luò)，j大于等于i）孟辑，玩家A拿硬幣只有兩種拿法哎甲，從左拿或者從右拿。如果從左拿饲嗽，則A能拿到的最大面值=拿到的這枚硬幣的面值 + 剩余區(qū)間的總面值 - B玩家在剩余區(qū)間能拿到的最大面值炭玫；A從右拿的情況與從左拿類似。由此我們可以得到狀態(tài)轉(zhuǎn)移方程貌虾。而通過兩次循環(huán)我們能夠得到長(zhǎng)度為n的序列里任意i到j(luò)區(qū)間的面值總和吞加，以及j=i的情況下先手玩家拿到的最大值（即第i個(gè)硬幣的面值）。
代碼：
