狀態(tài)轉(zhuǎn)移方程

從之前某個(gè)階段的某個(gè)或某些狀態(tài)狀態(tài)到下一個(gè)狀態(tài)之間的關(guān)系式钱贯，就叫做狀態(tài)轉(zhuǎn)移方程煤惩。

最優(yōu)子結(jié)構(gòu)

每個(gè)階段的最優(yōu)狀態(tài)可以從之前某個(gè)階段的某個(gè)或某些狀態(tài)直接得到的性質(zhì)叫做最優(yōu)子結(jié)構(gòu)毙籽。
最優(yōu)子結(jié)構(gòu)的產(chǎn)生往往是對(duì)狀態(tài)轉(zhuǎn)換方程結(jié)果的挑選势腮。

無后效性

如果一個(gè)問題被劃分各個(gè)階段之后买乃，階段I中的狀態(tài)只能由階段i-1中（或多個(gè)有限歷史階段）的狀態(tài)通過狀態(tài)轉(zhuǎn)移方程得來锈死，與其它狀態(tài)沒有關(guān)系，特別是與未發(fā)生的狀態(tài)沒有關(guān)系掸宛。

上述三項(xiàng)都在講同一個(gè)問題：該問題擁有遞推式死陆。該遞推式就是狀態(tài)轉(zhuǎn)移方程，該遞推式的等號(hào)右邊下標(biāo)都不會(huì)大于等號(hào)左邊唧瘾。

重疊子問題

動(dòng)態(tài)規(guī)劃將問題分解為子問題（一般兩個(gè)）措译。然后子問題又會(huì)分解出子子問題，這些子問題的解都被存儲(chǔ)起來劈愚，相同子問題的解將被重復(fù)利用瞳遍。
這些子問題解的的時(shí)候從多個(gè)備選結(jié)果中選擇最優(yōu)的那個(gè)（比如最小，最大菌羽，之類的）掠械。

備忘錄

應(yīng)該是所有動(dòng)態(tài)規(guī)劃為提中必備的一項(xiàng)。
該項(xiàng)是子問題注祖，也就是存儲(chǔ)了每個(gè)狀態(tài)猾蒂。

1. 鋼條切割：使用一維容器存儲(chǔ)了不同長(zhǎng)度鋼條的利潤(rùn)
2. 矩陣鏈乘法：每個(gè)子問題都有一個(gè)開始位置和結(jié)束位置，所以需要使用二維容器來存儲(chǔ)是晨。
3. 最長(zhǎng)公共子序列：每個(gè)字問題：第一個(gè)序列的結(jié)束位置肚菠，第二個(gè)序列的結(jié)束位置，所以也使用二維容器來存儲(chǔ)罩缴。

大白話

動(dòng)態(tài)規(guī)劃是一種尋找問題最優(yōu)解的方法蚊逢。
這種方法將一個(gè)問題從狀態(tài)的角度進(jìn)行定義，同時(shí)定義前一個(gè)狀態(tài)到后一個(gè)狀態(tài)的狀態(tài)轉(zhuǎn)移方程箫章，并存儲(chǔ)每一個(gè)狀態(tài)的最優(yōu)解烙荷。以便后續(xù)狀態(tài)使用。

上面這句話的意思其實(shí)就是：

保持問題給出的條件不變檬寂，但是改變問題的問法：

1. 在鋼條切割問題中终抽，不同長(zhǎng)度鋼條的售價(jià)不變，但是將問題改為當(dāng)鋼條1米的時(shí)候，怎樣利潤(rùn)最大昼伴，2米的時(shí)候曾陽利潤(rùn)最大匾旭，3米，4米……一直到問題所問的米數(shù)圃郊。
2. 矩陣鏈乘法中价涝，各個(gè)矩陣大小不變，但問題改為其中連續(xù)兩個(gè)矩陣相乘時(shí)計(jì)算歩數(shù)最小是多少持舆，連續(xù)三個(gè)飒泻，連續(xù)四個(gè)，連續(xù)五個(gè)……一直到問題所問個(gè)數(shù)吏廉。
3. 在最長(zhǎng)公共子序列中，兩個(gè)子序列不變惰许，將問題改為是否存在長(zhǎng)度為1,2,3,4,5…的子序列長(zhǎng)度席覆。
   改變問題的問法，同時(shí)也改變了解題的思路汹买。從之前的狀態(tài)推后來的狀態(tài)佩伤。

在自底而上的方式中（遞推）
這種方式的實(shí)現(xiàn)符合上述。
在自上而下的方式中（遞歸）
這種方式的實(shí)現(xiàn)也仍然是求的最開始的狀態(tài)然后推后來的狀態(tài)晦毙。

鋼條切割問題

一家公司購買長(zhǎng)鋼條生巡，將其切割成短鋼條出售，切割本身沒有成本见妒，長(zhǎng)度為i的短鋼條的價(jià)格為Pi孤荣。那給定一段長(zhǎng)度為n的鋼條和一個(gè)價(jià)格表Pi,求鋼條的切割方案使得收益Rn最大。如一個(gè)Pi如下：
長(zhǎng)度i 1 2 3 4 5 6 7 8 9 10
價(jià)格Pi 1 5 8 9 10 17 17 20 24 30

采用上述來分析：
鋼條長(zhǎng)度為：1 不切割须揣，2 不切割盐股， 3不切割 ，4 切割2+2耻卡，5 切割2+3……

同時(shí)應(yīng)該存儲(chǔ)每個(gè)狀態(tài)（鋼條長(zhǎng)度）的最大值：
自底而上：

int cal(const std::vector<int> lp, int len)
{
    lpLen = lp.size() - 1;
    int num(0);                             //記錄循環(huán)次數(shù)
    std::vector<int> p(len+1);              //建立備忘
    for(int i=1; i <= len; i++)             //i代表長(zhǎng)度疯汁，從1開始建立備忘
    {
        tmp = 0;
        if ( i <= lpLen )                      //讓i<lpLen的時(shí)候，備忘錄還不可用
        {
            for(int j = 0 ; j <= i;j++)
            {
                num++;
                tmp  = tmp > lp[j] + lp[i-j] ? tmp : lp[j] + lp[i-j];
            }
        }else{                              //長(zhǎng)度>lpLen以后備忘錄已經(jīng)可用了卵酪。
            for(int j = 1 ; j < i/2 +1;j++)
            {
                num++;
                tmp  = tmp > p[j] + p[i-j] ? tmp : p[j] + p[i-j];
            }
        }
        p[i] = tmp;                         //當(dāng)確定找到了最大值幌蚊，才添加
    }
    std::cout<<"num : "<<num<<std::endl;
    return p[len];
}

在一邊存一邊讀取備忘錄的時(shí)候，備忘錄什么時(shí)候可用是一個(gè)坑：

1. 剛開始溃卡，備忘錄中全是0溢豆，根本不能用。
2. 只有當(dāng)基本的方式都全了以后才可用塑煎。
   也就是lp中可能的切割方式沫换。
3. 當(dāng)長(zhǎng)度>能夠賣出的最長(zhǎng)長(zhǎng)度時(shí)，不存在不切割這種情況，所以j從1開始讯赏。
   但是垮兑，當(dāng)長(zhǎng)度小于等于賣出的最長(zhǎng)長(zhǎng)度時(shí)，是可以不切割的漱挎。

同時(shí)系枪，切割的長(zhǎng)度只需要從開始到總長(zhǎng)度的一半即可，因?yàn)榍懈钍菍?duì)稱的磕谅。

另外私爷，代碼中的lpLen使用其實(shí)是錯(cuò)的：
代碼中l(wèi)pLen假設(shè)的是基本的切割方式組合。但是實(shí)際中可能并不是和lpLen相等膊夹。
代碼中的lpLen應(yīng)該換成基本切割方式衬浑。比如如果將本題中5對(duì)應(yīng)的利潤(rùn)改為16,那么就會(huì)有11中基本切割方式。此時(shí)代碼的結(jié)果是錯(cuò)的放刨。
如果我們不能知道問題的輸入（也就是給定的條件）那么一般不能使用該方法工秩。

自上而下

//子上而下
int cut(const std::vector<int> &lp, std::vector<int> &p ,int len)
{
    int tmp = 0;    
    if(p[len] > 0) return p[len];       //使用備忘錄
    if(len == 0) return 0;              //0的時(shí)候出點(diǎn)

    if(len <= 10)
    {
        for(int i = 0;i <= len; i++)
        {
            tmp = std::max(tmp, lp[len-i]+lp[i]);
        }
    }else{
        for(int i = 1 ;i <= len/2 +1 ; i++)
        {                               //這里兩個(gè)都必須是cut*****
            tmp = std::max(tmp,cut(lp,p,i)+cut(lp,p,len-i) );
        }
    }
    p[len]=tmp;
    return p[len];
}
int calT(const std::vector<int> lp , int len)
{
    std::vector<int> p(len+1);
    return cut(lp,p,len);
}

其中標(biāo)*****的：
必須使用cut的原因是：此時(shí)備忘錄還沒建好，不能使用備忘錄进统。所以必須使用cut助币。

對(duì)比這兩種方式

1. 兩種方式都需要先建立備忘錄。
2. 子上而下的遞歸螟碎，并不需要去假設(shè)總共可能的基本切割方式眉菱。
   但是自底而上的遞推需要提前計(jì)算出基本的切割方式。

鋼條切割問題的最優(yōu)子結(jié)構(gòu)和狀態(tài)轉(zhuǎn)換方程：

//i表示未切割部分長(zhǎng)度掉分，j表示切割的長(zhǎng)度
f[i]=f[i-j]+max(f[j])

子問題重疊：
比如俭缓，固定米數(shù)鋼條的最大利潤(rùn)是一樣的。

矩陣鏈乘法

在該問題中叉抡，狀態(tài)和子問題為：從在給定的矩陣鏈中尔崔，取連續(xù)的1,2,3,4,5個(gè)矩陣相乘的歩數(shù)。
比如褥民，矩陣為：1015 1530 305 515 15*20
上述五個(gè)矩陣相乘季春。

當(dāng)取1個(gè)的時(shí)候相乘的計(jì)算歩數(shù) 為0 。
2個(gè)時(shí)消返，一共有4中情況
3個(gè)時(shí)载弄，一共有3中情況
4個(gè)時(shí)，一共兩種情況
5個(gè)時(shí)撵颊，就一種情況

在3個(gè)矩陣相乘時(shí)宇攻，每一種情況都會(huì)用到2個(gè)矩陣相的結(jié)果，并從中選取最少歩數(shù)的結(jié)果倡勇。

#include <limits.h>
#include <iostream>
#include <algorithm>
#include <vector>

int mulM(const std::vector<int> vec)
{
    int len = vec.size();
    int tmp = 0;
    int vecNum = len - 1;                       //實(shí)際矩陣個(gè)數(shù)
    std::vector<std::vector<int>> memo(len);    //備忘錄

    for(int i = 0 ;i < memo.size() ; i++)
    {
            memo[i].resize(len);
    }

    for(int len = 2 ;len <=  vecNum  ; len++)   //狀態(tài)：長(zhǎng)度從2開始逞刷。
    {                                           //長(zhǎng)為2的矩陣鏈在原矩陣鏈中的開始位置
        for(int start = 1 ; start <= vecNum - len + 1 ;start++ )
        {
            tmp=INT_MAX;
            int end = start + len -1;

            for(int k =  start ; k <= end -1  ; k++)    //括號(hào)的位置
            {
                int memo1=memo[start][k];
                int memo2=memo[k+1][end];
                tmp = std::min(tmp,vec[start-1] * vec[k] * vec[start+len-1] + memo1 + memo2);
                memo[start][end] = tmp;
            }
        }
    }
    for(int i = 0 ;i <= memo.size()-1 ; i++)
    {
        std::cout<<std::endl;
        for(int j = 0 ; j < memo[i].size(); j++)
        {
            std::cout<<memo[i][j]<<" ";
        }
        std::cout<<std::endl;
    }
    return memo[1][vecNum];
}

代碼講解

備忘錄中存儲(chǔ)的是memo[start][end]在原有矩陣鏈中從start到end位置的子矩陣鏈相乘的最短歩數(shù)。

最長(zhǎng)公共子序列

該問題也有用最優(yōu)子結(jié)構(gòu)：在某個(gè)公共子序列的基礎(chǔ)上推更長(zhǎng)的最優(yōu)子結(jié)構(gòu)。
這個(gè)的狀態(tài)轉(zhuǎn)換公式貌似不好寫吧夸浅？

狀態(tài)和子問題就變?yōu)椋寒?dāng)在兩個(gè)序列長(zhǎng)度從1開始慢慢增長(zhǎng)仑最，其公共子序列最大是多少？
那備忘錄也就是要記錄兩個(gè)公共子序列的長(zhǎng)度帆喇，所以需要一個(gè)二維容器警医。
備忘錄中memo[i][j],當(dāng)?shù)谝粋€(gè)序列長(zhǎng)i，第二個(gè)序列長(zhǎng)j情況下的最長(zhǎng)公共子系列坯钦。

這里其實(shí)也并不需要一個(gè)二外的容器预皇。遍歷仍然可以獲得。
這樣我們可以得到兩個(gè)序列的最大公共子序列的長(zhǎng)度婉刀，但是無法獲得其值吟温，所以有需要一個(gè)容器來存儲(chǔ)相等的部分。

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

std::string lcs(const std::string &l,const std::string &r)
{

    int ll = l.size();
    int rl = r.size();

    std::vector<std::vector<int> > memo(ll+1,std::vector<int>(rl+1));
    std::vector<std::vector<int> > memoRebuild(ll+1,std::vector<int>(rl+1));

    for(int inL = 1; inL <= ll ;inL ++)
    {
        for(int inR = 1; inR <= rl ;inR ++)
        {
            if(l[inL-1] == r[inR-1])
            {
                memo[inL][inR] = memo[inL-1][inR-1]+1;
                memoRebuild[inL][inR]=3;
            }else if(memo[inL][inR-1] > memo[inL-1][inR]){
                memo[inL][inR]=memo[inL][inR-1];
               memoRebuild[inL][inR]=2;
            }else{
                memo[inL][inR]=memo[inL-1][inR];
                memoRebuild[inL][inR]=1;
            }
       }
   }
    int reL = memoRebuild.size()-1;
    int reR = memoRebuild[0].size()-1;
    std::string re;
    while(reL >= 0 &&  reR >= 0)
    {
        if(memoRebuild[reL][reR]==3)
        {
            re.push_back(l[reL-1]);
            reL--; reR--;
        }else if(memoRebuild[reL][reR] == 1)
        {
            reL--;
        }else{
            reR--;
        }
    }
    std::cout<<"result ; "<<re<<std::endl;
    return re;
}

從上面的代碼中突颊，不難發(fā)現(xiàn)溯街，其實(shí)構(gòu)造好備忘錄才是本質(zhì)