動態(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ī)劃問題主要有以下幾個步驟：

1. 定義子問題。
2. 只考慮當前情況下，枚舉所有的可能，然后選擇一個最好的。
3. 解決相關(guān)的子問題。
4. 使用遞歸+記憶化的方式解決，或者使用動態(tài)規(guī)劃表，自底向上的解決。這里需要檢查子問題是不是有環(huán)的。
5. 解決基本情況。

時間復(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é)果進行處理，因為，這里求的是先手比后手多的值。

首先，在定義好子問題后，我們分析如何利用上面的套路來解決這個問題。

1. 對于狀態(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">。當前狀態(tài)的值為兩個值中較大的。
2. 從上面的狀態(tài)轉(zhuǎn)移，可知，狀態(tài)的轉(zhuǎn)移是單向的，是無環(huán)的。
3. 如果只有一張牌了，那么當前狀態(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ù)。