動態(tài)規(guī)劃我一直感覺有點難颖榜，主要原因是感覺每次都需要具體問題具體分析。聽了《算法導(dǎo)論》的課程述召，感覺自己從中學(xué)到了一點套路朱转，于是就想寫下來，和大家分享一下积暖。
動態(tài)規(guī)劃通常用來求解最優(yōu)化問題藤为，并且，求解的問題需要滿足兩個要素：最優(yōu)子結(jié)構(gòu)和子問題重疊夺刑。
動態(tài)規(guī)劃的基本套路
課堂上老師對于動態(tài)規(guī)劃的理解是：
- 動態(tài)規(guī)劃 = 小心的暴力枚舉缅疟。（DP = “careful brute force”）
- 動態(tài)規(guī)劃 = 枚舉 + 遞歸 + 記憶化。（DP = guessing + recursion + memorization）
解決動態(tài)規(guī)劃問題主要有以下幾個步驟：
- 定義子問題遍愿。
- 只考慮當(dāng)前情況下存淫，枚舉所有的可能，然后選擇一個最好的沼填。
- 解決相關(guān)的子問題桅咆。
- 使用遞歸+記憶化的方式解決，或者使用動態(tài)規(guī)劃表坞笙，自底向上的解決岩饼。這里需要檢查子問題是不是有環(huán)的荚虚。
- 解決基本情況。
時間復(fù)雜度 = 子問題的個數(shù) * 解決子問題花費的時間籍茧。
這里最難的一點是定義子問題版述。如果輸入是字符串或者數(shù)組的時候，子問題通常為下面三種情況之一：
- 后綴寞冯，從i開始到字符串結(jié)尾渴析。
- 前綴，從0開始到i吮龄。
- 子串俭茧，從i到j(luò)。
對于子問題的定義會影響算法的復(fù)雜度螟蝙』帜眨考慮下面這個問題。
給定一個整型數(shù)組arr胰默，代表數(shù)值不同的紙牌排成一條線场斑，玩家A和玩家B依次拿走每張紙牌，規(guī)定玩家A先拿牵署，玩家B后拿漏隐，但是每個玩家每次只能拿走最左和最右的紙牌，玩家A和玩家B絕頂聰明奴迅。請返回最后的獲勝者的分數(shù)青责。
上面這個題目時左程云書中的一個題目，他給出的解答是用了兩個遞歸函數(shù)取具，也就是脖隶，子問題劃分為兩種情況，在上先手最后獲得分數(shù)暇检，和在
上后手獲得的分數(shù)产阱。但后來我看到了另外一種解法，就是把子問題定義在
上先手比后手多獲得的分數(shù)块仆。這樣构蹬，子問題的數(shù)量就減少了，但最后還需對結(jié)果進行處理悔据，因為庄敛，這里求的是先手比后手多的值。
首先科汗，在定義好子問題后藻烤，我們分析如何利用上面的套路來解決這個問題。
- 對于狀態(tài)
，都只有兩種選擇隐绵，選擇前面的和后面的之众，如果選擇前面的，狀態(tài)變?yōu)榱?img class="math-inline" src="https://math.jianshu.com/math?formula=(i%2B1%2Cj)" alt="(i+1,j)" mathimg="1">依许，如果選擇后面的，狀態(tài)變?yōu)榱?img class="math-inline" src="https://math.jianshu.com/math?formula=(i%2Cj-1)" alt="(i,j-1)" mathimg="1">缀蹄。當(dāng)前狀態(tài)的值為兩個值中較大的峭跳。
- 從上面的狀態(tài)轉(zhuǎn)移，可知缺前，狀態(tài)的轉(zhuǎn)移是單向的蛀醉，是無環(huán)的。
- 如果只有一張牌了衅码，那么當(dāng)前狀態(tài)的值就為這張牌的值拯刁。
從上面的分析，寫出的代碼如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 0x07FFFFFFF
int guess(vector<int> &iterms, int left, int right, vector<vector<int> > &dp){
if(left == right){ /* 只有一個逝段，先手可以拿完 */
dp[left][right] = iterms[left];
}
if(dp[left][right] == INF){
/* 可以拿左邊的垛玻，也可以拿右邊的，取最大值 */
dp[left][right] = max(iterms[left] - guess(iterms,left+1,right,dp),iterms[right] - guess(iterms,left,right-1,dp));
}
return dp[left][right];
}
int stoneGame(vector<int>& iterms) {
if(iterms.size() == 0){
return 0;
}
/* dp代表只考慮序列i,j的情況下奶躯，先手比后手多的值 */
vector<vector<int> > dp(iterms.size(),vector<int>(iterms.size(),INF));
guess(iterms,0,iterms.size()-1,dp);
return dp[0][iterms.size()-1];
}
int main(int argc, char const *argv[])
{
int n,num;
cin>>n;
vector<int> v;
int sum = 0;
for(int i=0;i<n;i++){
cin>>num;
v.push_back(num);
sum += num;
}
int ret = stoneGame(v);
if(ret < 0){ /* 先手可能會輸 */
ret = - ret;
}
sum = (sum - ret) / 2 + ret;
cout<<sum<<endl;
system("pause");
return 0;
}
在看下面一個問題帚桩。
給定兩個字符串str1和str2，再給定三個整數(shù)ic嘹黔，dc和rc账嚎，分別代表插入、刪除和替換一個字符的代價儡蔓，請輸出將str1編輯成str2的最小代價郭蕉。
這里就直接給出代碼。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 0x07FFFFFFF
int minCostGuess(string &s1, string &s2, int l1, int l2, int ic,int dc,int rc,vector<vector<int> > &dp){
if(l1 == s1.size()){
//只能插入
dp[l1][l2] = (s2.size() - l2)*ic;
}else if(l2 == s2.size()){
//只能刪除
dp[l1][l2] = (s1.size() - l1) * dc;
}
if(dp[l1][l2] == INF){ //沒有算出來
int res = INF;
res = min(res,ic + minCostGuess(s1,s2,l1,l2+1,ic,dc,rc,dp)); // 插入
res = min(res,dc + minCostGuess(s1,s2,l1+1,l2,ic,dc,rc,dp)); // 刪除
if(s1[l1] == s2[l2]){
rc = 0; //如果相同喂江，替換的代價為0
}
res = min(res,rc + minCostGuess(s1,s2,l1+1,l2+1,ic,dc,rc,dp)); // 替換
dp[l1][l2] = res;
}
return dp[l1][l2];
}
int minCost(string &s1, string &s2, int ic,int dc,int rc){
vector<vector<int> > dp(s1.size()+1,vector<int>(s2.size()+1,INF));
minCostGuess(s1,s2,0,0,ic,dc,rc,dp);
return dp[0][0];
}
int main(int argc, char const *argv[])
{
string s1,s2;
int ic,dc,rc;
cin>>s1>>s2>>ic>>dc>>rc;
cout<<minCost(s1,s2,ic,dc,rc)<<endl;
system("pause");
return 0;
}
上面的代碼去耪傩猓客網(wǎng)測試，發(fā)現(xiàn)時間超了（但我多試了幾次开呐，發(fā)現(xiàn)有時候能夠過）烟勋，所以，有時候?qū)懗鲞@種記憶化遞歸版本并不能通過筐付，還需要對其進行優(yōu)化卵惦。
動態(tài)規(guī)劃的優(yōu)化——使用動態(tài)規(guī)劃表、空間優(yōu)化
int minCost(string s1,string s2,int ic,int dc,int rc){
int n = s1.size();
int m = s2.size();
vector<vector<int>> dp(n +1 ,vector<int>(m+1,0));
for(int i=1;i<=m;i++){
dp[0][i] = ic * i;
}
for(int i=1;i<=n;i++){
dp[i][0] = dc * i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j] = min(dp[i][j-1] + ic,dp[i-1][j] + dc);
int tmp = s1[i-1] == s2[j-1]?dp[i-1][j-1]:dp[i-1][j-1] + rc;
dp[i][j] = min(dp[i][j],tmp);
}
}
return dp[n][m];
}
未完待續(xù)瓦戚。
