一养晋、導(dǎo)論

?動(dòng)態(tài)規(guī)劃（Dynamic Programming衬吆，DP）是算法設(shè)計(jì)思想中最難也是最有趣的部分。掌握動(dòng)態(tài)規(guī)劃算法绳泉，對(duì)于大廠面試是必不可少的逊抡。有接觸過(guò)DP的小伙伴也許會(huì)聯(lián)想到許許多多的名詞，如什么狀態(tài)轉(zhuǎn)移方程什么的零酪；要不就想到教材書(shū)上嚴(yán)謹(jǐn)而又晦澀難懂的對(duì)于動(dòng)態(tài)規(guī)劃的介紹冒嫡；也有人想到高中的通項(xiàng)公式或數(shù)列題等等，但是左看右看都看不出動(dòng)態(tài)體現(xiàn)在哪四苇？哈哈孝凌，按照MIT編程導(dǎo)論老師的說(shuō)法，就是創(chuàng)建人為了不讓軍方知道他在做什么而故意胡謅的一個(gè)名詞月腋。后續(xù)了解有關(guān)算法的實(shí)現(xiàn)蟀架，我們或許可以用分步規(guī)劃法、分步存儲(chǔ)法榆骚、遞推存儲(chǔ)法片拍、數(shù)列遞推法、狀態(tài)轉(zhuǎn)移法等等來(lái)重命名它妓肢。
?其實(shí)捌省，小編本人掌握動(dòng)態(tài)規(guī)劃的過(guò)程，也是一波三折碉钠，經(jīng)歷九九八十一難纲缓。接下來(lái)卷拘，小編借助幾個(gè)例子，談?wù)勛约簩?duì)DP算法的一點(diǎn)理解色徘。

二恭金、斐波那契數(shù)列看DP思想

?斐波那契數(shù)列：0，1褂策，1横腿，2，3斤寂，5耿焊，8，13遍搞，21罗侯，34，55溪猿，89钩杰，144，233 ……
?它遵循這樣的規(guī)律：當(dāng)前值為前兩個(gè)值的和诊县。那么第n個(gè)值為多少讲弄？
?這其實(shí)是一個(gè)數(shù)列，學(xué)過(guò)數(shù)列的小伙伴應(yīng)該知道依痊，如果數(shù)列{a_n}的第n項(xiàng)與它前一項(xiàng)或幾項(xiàng)的關(guān)系可以用一個(gè)式子來(lái)表示避除，那么這個(gè)公式叫做這個(gè)數(shù)列的遞推公式。那么斐波那契數(shù)列的遞推公式就是f(n)=f(n-1)+f(n-2)胸嘁。我們來(lái)分析下問(wèn)題的解決方法瓶摆。

（一）暴力遞歸

?我們常見(jiàn)的是使用暴力遞歸的算法來(lái)解決這個(gè)問(wèn)題，代碼如下：

#include<iostream>
using namespace std;
int Fib(int n)//遞歸
{
    if(n<0)
        cout<<"n<0性宏，data error!"<<endl;
    else if(n==1 || n==2)
        return 1;
    else{
        return Fib(n-1)+Fib(n-2);
    }
    return 0;
    
}
int main()
{
    int n,ret=0;
    cout<<"請(qǐng)輸入下標(biāo):";
    cin>>n;
    ret=Fib(n);
    cout<<"遞歸值："<<ret<<endl;
    return 0;
 } 

?有關(guān)遞歸算法的講解可參考小編的另一篇文章遞歸算法詳解群井。
?如上所示，代碼簡(jiǎn)單易懂毫胜，然而代碼卻極其低效书斜。這種使用遞歸的方式一方面不僅造成棧空間的極大浪費(fèi)指蚁，另一方面該算法的時(shí)間復(fù)雜度為O(2ⁿ)菩佑，指數(shù)級(jí)別。我們可以看下f(20)的求解過(guò)程凝化，這其實(shí)就是一棵樹(shù)稍坯。可以看到 f(18) 被計(jì)算了兩次，而且你可以看到瞧哟，以 f(18) 為根的這個(gè)遞歸樹(shù)體量巨大混巧，多算一遍，會(huì)耗費(fèi)巨大的時(shí)間勤揩。更何況咧党，還不止 f(18) 這一個(gè)節(jié)點(diǎn)被重復(fù)計(jì)算，隨著遞歸的深入陨亡，計(jì)算任務(wù)不斷翻倍傍衡，所以這個(gè)算法及其低效。

遞歸樹(shù)

（二）自頂向下的記憶化搜索遞歸

?即然耗時(shí)的原因是重復(fù)計(jì)算遮糖，那么我們可以造一個(gè)數(shù)組绣的，每次算出某個(gè)子問(wèn)題的答案后別急著返回，先記到數(shù)組里再返回欲账；每次遇到一個(gè)子問(wèn)題先去數(shù)組里查一查屡江，如果發(fā)現(xiàn)之前已經(jīng)解決過(guò)這個(gè)問(wèn)題了，直接把答案拿出來(lái)用赛不，不要再耗時(shí)去計(jì)算了惩嘉。
?代碼如下：

#include<iostream>
#include<vector>
using namespace std;
int helper(vector<int>& result,int n){
    if(n==1)return 1;
    if(n==2)return 2;
    if(result[n]!=0)return result[n];
    result[n]=helper(result,n-1)+helper(result,n-2);
    return result[n];
}
int Fib(int N){
    if(N<1) return 0;//小于1，不正確 
    vector<int> result(N+1,0);//創(chuàng)建長(zhǎng)度為N+1的數(shù)組 俄删，初始化為0 
    return helper(result,N);
}
int main()
{
    int n,ret=0;
    cout<<"請(qǐng)輸入下標(biāo):";
    cin>>n;
    ret=Fib(n);
    cout<<"遞歸值："<<ret<<endl;
    return 0;
 } 

?*"記憶化搜索"或者我們稱(chēng)"重疊子問(wèn)題"的加緩存優(yōu)化的實(shí)現(xiàn)宏怔，我們的思考路徑是"自頂向下"奏路。即為了解決數(shù)據(jù)規(guī)模大的問(wèn)題畴椰，我們“假設(shè)”已經(jīng)解決了數(shù)據(jù)規(guī)模較小的子問(wèn)題。我們沒(méi)有從最基本的問(wèn)題開(kāi)始求解鸽粉，對(duì)于f(n)=f(n-1)+f(n-2)斜脂，我們假裝f(n-1)和f(n-2)是已知的。現(xiàn)在触机，畫(huà)出圖帚戳，你就知道數(shù)組到底做了什么。

記憶化搜索

剪枝

（三）自底向上的動(dòng)態(tài)規(guī)劃思想

?有了上一步的啟發(fā)，我們可以把這個(gè)數(shù)組獨(dú)立出來(lái)成為一張表鄙皇。
?① 斐波那契數(shù)列有這樣的關(guān)系：f(n)=f(n-1)+f(n-2)
?② 我們使用一個(gè)數(shù)組result[ ]厦凤，來(lái)緩存這些重復(fù)計(jì)算的值。
?因此有：result[i]= result[i-1]+ result[i-2]育苟。采用這樣的方法我們就可以對(duì)緩存的數(shù)據(jù)進(jìn)行復(fù)用较鼓。
?③ 按順序從小往大算。使用for循環(huán)實(shí)現(xiàn)了從0到n的順序求解违柏，問(wèn)題從小規(guī)模往大規(guī)模求解的順序走博烂。

DP思想

#include<iostream>
#include<vector>
using namespace std;
int Fib(int N){
    if(N<1) return 0;
    vector<int> result(N+1,0);
    result[1]=1;
    result[2]=2;
    for(int i=3;i<=N;i++){
        result[i]=result[i-1]+result[i-2];
    }
    return result[N];
}
int main()
{
    int n,ret=0;
    cout<<"請(qǐng)輸入下標(biāo):";
    cin>>n;
    ret=Fib(n);
    cout<<"遞歸值："<<ret<<endl;
    return 0;
 } 

?同樣的，時(shí)間復(fù)雜度降為O(n)漱竖。
?其實(shí)禽篱，上述斐波那契數(shù)列就是使用了DP思想來(lái)解決這個(gè)問(wèn)題。

（四）動(dòng)態(tài)規(guī)劃思想解決問(wèn)題的三步驟

?① 建立遞推公式
?② 根據(jù)遞推公式建立一個(gè)數(shù)組馍惹，用來(lái)緩存并復(fù)用以往結(jié)果
?③ 運(yùn)用循環(huán)控制結(jié)構(gòu)躺率，按順序從小往大算，得到最終結(jié)果
?當(dāng)然万矾，這里的遞推公式悼吱，在DP里稱(chēng)呼為狀態(tài)轉(zhuǎn)移方程，數(shù)組又稱(chēng)呼為DP表良狈。往下看后添，小編稍后還會(huì)進(jìn)行解釋。

三薪丁、湊硬幣問(wèn)題探DP性質(zhì)

?當(dāng)然遇西，DP思想主要使用在求解最值問(wèn)題這一類(lèi)問(wèn)題上，上述斐波那契數(shù)列只不過(guò)是用來(lái)描述下DP思想解決問(wèn)題的基本的步驟及其使用價(jià)值严嗜。
?現(xiàn)在有面值為1粱檀，5，11的硬幣若干÷現(xiàn)在您的目標(biāo)是湊出某個(gè)金額w茄蚯，需要用到盡量少的硬幣。

（一）“貪心”能解決？

?依據(jù)生活經(jīng)驗(yàn)第队，我們每次都是先挑面值大的硬幣哮塞，按這樣的方法來(lái)湊夠金額。這就是所謂的“貪心策略”凳谦。我們面對(duì)的局面是“需要湊出w”忆畅，貪心策略會(huì)盡快讓w變得更小。能讓w少11就盡量讓它少11尸执，這樣我們接下來(lái)面對(duì)的局面就是湊出w-11家凯。長(zhǎng)期的生活經(jīng)驗(yàn)表明，貪心策略是正確的如失。
?但是绊诲，如果我們要用這些面值的硬幣湊出15元時(shí)，會(huì)發(fā)現(xiàn)：
?貪心策略：15=1×11+4×1（貪心策略使用了5個(gè)硬幣）
?然而15=3×5褪贵，正確的策略只需要用3個(gè)硬幣掂之。為什么會(huì)這樣呢？貪心策略錯(cuò)在了哪里脆丁？
?剛剛已經(jīng)說(shuō)過(guò)世舰，貪心策略的綱領(lǐng)是：“盡量使接下來(lái)面對(duì)的w更小”。這樣槽卫，貪心策略在w=15的局面時(shí)跟压，會(huì)優(yōu)先使用11來(lái)把w降到4；但是在這個(gè)問(wèn)題中歼培，湊出4的代價(jià)是很高的震蒋，必須使用4×1。如果使用了5躲庄，w會(huì)降為10查剖，雖然沒(méi)有4那么小，但是湊出10只需要兩張5元读跷。在這里我們發(fā)現(xiàn)梗搅，貪心是一種只考慮眼前情況的策略禾唁。也就是所謂的鼠目寸光效览。

（二）尋找遞推關(guān)系

?那么，現(xiàn)在我們?cè)鯓硬拍鼙苊馐竽看绻饽氐炊蹋咳绻苯颖┝γ杜e湊出w的方案丐枉，明顯復(fù)雜度過(guò)高。太多種方法可以湊出w了掘托，枚舉它們的時(shí)間是不可承受的瘦锹。我們現(xiàn)在來(lái)嘗試找一下性質(zhì)。
?重新分析剛剛的例子。w=15時(shí)弯院，我們?nèi)绻?1辱士，接下來(lái)就面對(duì)w=4的情況；如果取5听绳，則接下來(lái)面對(duì)w=10的情況颂碘。我們發(fā)現(xiàn)這些問(wèn)題都有相同的形式：“給定w，湊出w所用的最少硬幣是多少個(gè)椅挣？”
?我們用f(n)來(lái)表示“湊出n所需的最少硬幣數(shù)量”头岔。
?那么，如果我們?nèi)×?1鼠证，最后的代價(jià)（湊出來(lái)的總硬幣個(gè)數(shù)）是多少呢峡竣？
?明顯f(15)=f(15-11)+1=f(4)+1=4+1=5，它的意義是：利用11來(lái)湊出15量九，付出的代價(jià)等于f(4)加上自己這一枚硬幣∈赎現(xiàn)在我們暫時(shí)不管f(4)怎么求出來(lái)。
?依次類(lèi)推荠列，馬上可以知道：如果我們用5來(lái)湊出15攻谁，cost就是f(15)=f(15-5)+1=f(10)+1=2+1=3；
? 那么弯予，現(xiàn)在w=15的時(shí)候戚宦，我們?cè)撊∧欠N硬幣呢？當(dāng)然是各種方案中锈嫩，代價(jià)最低的那一個(gè)受楼！
? 取11：f(15)=f(15-11)+1=f(4)+1=4+1=5;
? 取5 ：f(15)=f(15-5)+1=f(10)+1=2+1=3;
? 取1 ：f(15)=f(15-1)+1=f(14)+1=4+1=5;
? 顯而易見(jiàn)，f(15)值最低的是取5的方案呼寸。我們通過(guò)上面三個(gè)式子艳汽，做出了正確的決策！
? 這給了我們一個(gè)至關(guān)重要的啟示：f(n)只與f(n-11)对雪，f(n-5)河狐，f(n-1)有關(guān)，也就是：f(n)=min{ f(n-11), f(n-5), f(n-1) } +1
?這個(gè)遞推式子是非常激動(dòng)人心的瑟捣。我們要求出f(n)馋艺，只需要求出幾個(gè)更小的f值；既然如此迈套，我們從小到大把所有的f(i)求出來(lái)不就好了捐祠？注意一下邊界情況即可。

（三）編寫(xiě)程序

?代碼如下：

#include <iostream>
using namespace std;
#define INF  99999
int min(int x, int y, int z)
{
    if (x <= y && x <= z)
        return x;
    if (y <= x && y <= z)
        return y;
    if (z <= x && z <= y)
        return z;
}
int main()
{
    int coin[3] = { 1, 5, 11 };
    int dp[16] = {0};
 
    for (int i = 1; i < 16; i++)
    {
        int tmp[3] = { INF,INF,INF };
        if (i >= 1)
            tmp[0] = dp[i - 1] + 1;
        if (i >= 5)
            tmp[1] = dp[i - 5] + 1;
        if (i >= 11)
            tmp[2] = dp[i - 11] + 1;
        dp[i] = min(tmp[0], tmp[1], tmp[2]);
        cout << "dp["<<i<<"]=" << dp[i] << endl;
 
    }
 
    cout << "dp[15]=" << dp[15] << endl;
    return 0;
}

（四）一點(diǎn)歸納

?可以發(fā)現(xiàn)桑李，求出f(n)踱蛀，只需要知道幾個(gè)更小的f(c)窿给。我們將求解f(c)稱(chēng)作求解f(n)的“子問(wèn)題”。將一個(gè)問(wèn)題拆成幾個(gè)子問(wèn)題率拒，分別求解這些子問(wèn)題崩泡，即可推斷出大問(wèn)題的解兵钮。這就是DP（動(dòng)態(tài)規(guī)劃羽资，dynamic programming）。
?看看上述的分析卜壕，我們也可以來(lái)引入兩個(gè)新的概念：
?① 無(wú)后效性
?一旦f(n)確定寥掐，“我們?nèi)绾螠惓鰂(n)”就再也用不著了靴寂。觀察遞推公式可知，f(n)只與f(n-11)召耘，f(n-5)百炬，f(n-1)有關(guān)。我們只關(guān)心f(w)的值污它，不關(guān)心是怎么湊出w的剖踊。我們將f(n)定義為該問(wèn)題的”狀態(tài)”，該狀態(tài)是從之前某個(gè)階段的某個(gè)或某些狀態(tài)得到的衫贬。舉例子德澈，要求出f(15)，只需要知道f(14)固惯，f(10)梆造，f(4)的值，而f(14)葬毫，f(10)镇辉，f(4)是如何算出來(lái)的，對(duì)之后的問(wèn)題沒(méi)有影響贴捡。
“?未來(lái)與過(guò)去無(wú)關(guān)”忽肛，這就是無(wú)后效性。（嚴(yán)格定義：如果給定某一階段的狀態(tài)烂斋，則在這一階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響屹逛。）
?至于什么是階段，什么是狀態(tài)汛骂，稍后繼續(xù)來(lái)看罕模。
?② 最優(yōu)子結(jié)構(gòu)
?回顧我們對(duì)f(n)的定義：我們記“湊出n所需的最少硬幣數(shù)量”為f(n).
f(n)的定義就已經(jīng)蘊(yùn)含了“最優(yōu)”。利用w=14,10,4的最優(yōu)解香缺，我們即可算出w=15的最優(yōu)解手销。大問(wèn)題的最優(yōu)解可以由小問(wèn)題的最優(yōu)解推出，這個(gè)性質(zhì)叫做“最優(yōu)子結(jié)構(gòu)性質(zhì)”图张。
?因此一個(gè)問(wèn)題要想能夠使用DP思想解決锋拖，一方面看能否將大問(wèn)題拆成幾個(gè)小問(wèn)題，且滿(mǎn)足無(wú)后效性祸轮、最優(yōu)子結(jié)構(gòu)性質(zhì)兽埃。

四、DAG最短路徑觀多階段決策

?或許很多小伙伴對(duì)狀態(tài)轉(zhuǎn)移方程感到陌生适袜，啥是狀態(tài)柄错。當(dāng)然，這方面的內(nèi)容就跟數(shù)學(xué)有更大的聯(lián)系了苦酱。
?最短路徑問(wèn)題：在下面的線路網(wǎng)絡(luò)圖中售貌，從A至E有一批貨物需要調(diào)運(yùn)。圖上所標(biāo)數(shù)字為各節(jié)點(diǎn)之間的運(yùn)輸距離疫萤，為使總運(yùn)費(fèi)最少颂跨，必須找出一條由A至E總里程最短的路線。

線路網(wǎng)絡(luò)圖

最短路徑

五敬辣、最長(zhǎng)上升子序列窺DP解題思路

?最長(zhǎng)上升子序列（LIS）問(wèn)題：給定長(zhǎng)度為n的序列a雪标，從a中抽取出一個(gè)子序列零院，這個(gè)子序列需要單調(diào)遞增。問(wèn)最長(zhǎng)的上升子序列（LIS）的長(zhǎng)度村刨。
?例子： a[7] = {1,6,4,2,3,9,8}告抄，找到的最長(zhǎng)的上升子序列（LIS）為{1,2,3,9}或者{1,2,3,8}，長(zhǎng)度為4嵌牺。
? 思想：這里用到的是自底向上的尋找最優(yōu)子結(jié)構(gòu)的的思想打洼。粗俗來(lái)說(shuō)：如果你想要得到七個(gè)數(shù)里面的最長(zhǎng)子序列，你可以先找前6個(gè)數(shù)里面的最長(zhǎng)子序列逆粹，同理募疮，你又必須得找前5個(gè)數(shù)里面的最長(zhǎng)子序列，直到子序列為1僻弹。
?我們使用DP思想來(lái)解決這道問(wèn)題阿浓，關(guān)鍵的是要設(shè)定好狀態(tài)，找到狀態(tài)轉(zhuǎn)移方程蹋绽，找到初值和邊界條件芭毙，最后才能找到所需的答案。
?我們來(lái)分析下：
?數(shù)組d[i]:用數(shù)組d 來(lái)存儲(chǔ)前第i個(gè)數(shù)的最長(zhǎng)子序列卸耘，i表示的就前幾個(gè)數(shù)退敦。
?毫無(wú)疑問(wèn)有：
? {1}：d[1]=1 : 表示第一個(gè)數(shù)他的最長(zhǎng)子序列是1，最長(zhǎng)上升子序列為{1}
?{1,6}：d[2]=d[1]+1=2 : 表示前兩個(gè)數(shù)中鹊奖，最長(zhǎng)上升子序列長(zhǎng)度為2苛聘，最長(zhǎng)上升子序列為{1,6}
?{1,6,4}：d[3]=d[1]+1=2 : 因?yàn)? < 6 所以不能用d[2]+1,但 1<4 所以是d[1]+1，最長(zhǎng)上升子序列為 {1,6}和{1,4}
?{1,6,4,2} ：d[4]=d[1]+1=2 ：4和6 都大于2 所以不能用d[2]忠聚，d[3]设哗，最長(zhǎng)上升子序列為{1,6}，{1,4}和{1,2}
?{1,6,4,2,3} ：d[5]=d[4]+1=3 ：3 >2 两蟀，所以d[4]+1=2+1=3网梢，最長(zhǎng)上升子序列為{1,2,3}
? {1,6,4,2,3,9} ：d[6]=d[5]+1= 4 ：最長(zhǎng)上升子序列是{1,2,3,9}
?{1,6,4,2,3,9,8}：d[7]=4 ：最長(zhǎng)上升子序列是{1,2,3,9} 或者{1,2,3,8}
? 通過(guò)分析，我們得到
? 狀態(tài)：d[i]指在1~i這i個(gè)數(shù)中赂毯，必須包含a[i]這個(gè)數(shù)的最長(zhǎng)上升子序列战虏。
? 狀態(tài)轉(zhuǎn)移方程：if(a[j] < a[i]) d[i] = max(d[i], d[j] + 1)（1 <= j <= i - 1）
? 初值：d[i] = 1（一個(gè)數(shù)本身就是一個(gè)遞增序列）
? 答案：max{d[i]}
? 接下來(lái)，我們就可以來(lái)編寫(xiě)代碼了党涕，如下所示：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i,j,n,max;
    scanf("%d",&n);
    int a[n+1],d[n+1];
    for(i=1;i<=n;++i)
        scanf("%d",&a[i]);
    d[1]=1;
    for(i=2;i<=n;++i)
    {
        max=d[1];
        for(j=1;j<i;++j)
        {
            if(a[j]<a[i]&&d[j]>max)
                max=d[j];
        }
        d[i]=max+1;
    }
    max=0;
    for(i=1;i<=n;++i)
    {
        if(d[i]>max)
            max=d[i];
    }
    printf("%d\n",max);
    return 0;
} 

? 可以看到程序有兩個(gè)for循環(huán)烦感，時(shí)間復(fù)雜度為O(n²)。當(dāng)然我們還可以采取一些優(yōu)化手段膛堤，把時(shí)間復(fù)雜度降低到O(nlog_n)手趣，這里小編不做解釋。

六肥荔、DP解題的一般思路

? 通過(guò)上述幾個(gè)最簡(jiǎn)單的例子绿渣，我們可以了解到有關(guān)的DP思想朝群。動(dòng)態(tài)規(guī)劃所處理的問(wèn)題是一個(gè)多階段決策問(wèn)題，一般由初始狀態(tài)開(kāi)始中符，通過(guò)對(duì)中間階段決策的選擇姜胖，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列淀散，同時(shí)確定了完成整個(gè)過(guò)程的一條活動(dòng)路線(通常是求最優(yōu)的活動(dòng)路線)右莱。如圖所示。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式吧凉，一般要經(jīng)歷以下幾個(gè)步驟：
? （1）劃分階段：按照問(wèn)題的時(shí)間或空間特征隧出，把問(wèn)題分為若干個(gè)階段。在劃分階段時(shí)阀捅，注意劃分后的階段一定要是有序的或者是可排序的胀瞪，否則問(wèn)題就無(wú)法求解。
? （2）確定狀態(tài)和狀態(tài)變量：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)饲鄙。當(dāng)然凄诞，狀態(tài)的選擇要滿(mǎn)足無(wú)后效性。
? （3）確定決策并寫(xiě)出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系忍级，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)帆谍。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫(xiě)出轴咱。但事實(shí)上常常是反過(guò)來(lái)做汛蝙，根據(jù)相鄰兩個(gè)階段的狀態(tài)之間的關(guān)系來(lái)確定決策方法和狀態(tài)轉(zhuǎn)移方程。
? （4）尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式朴肺，需要一個(gè)遞推的終止條件或邊界條件窖剑。
? 一般，只要解決問(wèn)題的階段戈稿、狀態(tài)和狀態(tài)轉(zhuǎn)移決策確定了西土，就可以寫(xiě)出狀態(tài)轉(zhuǎn)移方程（包括邊界條件）。

七鞍盗、算法實(shí)現(xiàn)的一般步驟

? 1需了、創(chuàng)建一個(gè)一維數(shù)組或者二維數(shù)組，保存每一個(gè)子問(wèn)題的結(jié)果般甲，具體創(chuàng)建一維數(shù)組還是二維數(shù)組看題目而定肋乍，基本上如果題目中給出的是一個(gè)一維數(shù)組進(jìn)行操作，就可以只創(chuàng)建一個(gè)一維數(shù)組敷存，如果題目中給出了兩個(gè)一維數(shù)組進(jìn)行操作或者兩種不同類(lèi)型的變量值住拭，比如背包問(wèn)題中的不同物體的體積與總體積，找零錢(qián)問(wèn)題中的不同面值零錢(qián)與總錢(qián)數(shù)，這樣就需要?jiǎng)?chuàng)建一個(gè)二維數(shù)組滔岳。
?注：需要?jiǎng)?chuàng)建二維數(shù)組的解法，都可以創(chuàng)建一個(gè)一維數(shù)組運(yùn)用滾動(dòng)數(shù)組的方式來(lái)解決挽牢，即一位數(shù)組中的值不停的變化谱煤，后面會(huì)詳細(xì)徐敘述。
?2禽拔、設(shè)置數(shù)組邊界值刘离，一維數(shù)組就是設(shè)置第一個(gè)數(shù)字，二維數(shù)組就是設(shè)置第一行跟第一列的值睹栖，特別的滾動(dòng)一維數(shù)組是要設(shè)置整個(gè)數(shù)組的值硫惕，然后根據(jù)后面不同的數(shù)據(jù)加進(jìn)來(lái)變幻成不同的值。
? 3野来、找出狀態(tài)轉(zhuǎn)換方程恼除，也就是說(shuō)找到每個(gè)狀態(tài)跟他上一個(gè)狀態(tài)的關(guān)系，根據(jù)狀態(tài)轉(zhuǎn)化方程寫(xiě)出代碼曼氛。
?4豁辉、返回需要的值，一般是數(shù)組的最后一個(gè)或者二維數(shù)組的最右下角舀患。
?代碼基本框架：

for(j=1; j<=m; j=j+1) // 第一個(gè)階段
     xn[j] = 初始值;
for(i=n-1; i>=1; i=i-1)// 其他n-1個(gè)階段
     for(j=1; j>=f(i); j=j+1)//f(i)與i有關(guān)的表達(dá)式
        xi[j]=j=max（或min）{g(xi-1[j1:j2]), ......, g(xi-1[jk:jk+1])};
t = g(x1[j1:j2]); // 由子問(wèn)題的最優(yōu)解求解整個(gè)問(wèn)題的最優(yōu)解的方案
print(x1[j1]);
for(i=2; i<=n-1; i=i+1）
{
    t = t-xi-1[ji];
    for(j=1; j>=f(i); j=j+1)
        if(t=xi[ji])
             break;
}

?DP是一種思想徽级，一種“大事化小，小事化了”的思想聊浅。帶著這種思想餐抢，DP將會(huì)成為我們解決問(wèn)題的利器。
?上述是小編看了挺多資料自己總結(jié)的一點(diǎn)經(jīng)驗(yàn)低匙，由于能力不足所以有些理解的可能不是特別正確旷痕，也請(qǐng)指正，謝謝努咐！