資源描述：
《《dp入門講解》PPT課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、動(dòng)態(tài)規(guī)劃入門講解UESTC陳斐童什么是dynamicprogramming?Dp不是一種算法，而是一種思想。TopDownMethod遞歸的將問(wèn)題分解為更小的問(wèn)題。BottomUpMethod由初始狀態(tài)遞推得到目標(biāo)狀態(tài)。Dp的本質(zhì)是狀態(tài)和狀態(tài)轉(zhuǎn)移。做dp題的時(shí)候就是定義狀態(tài)，寫出轉(zhuǎn)移方程。Dp的條件是最優(yōu)子結(jié)構(gòu)和無(wú)后效性。不滿足這兩個(gè)條件的，思想又和dp相似的，叫搜索。狀態(tài)的定義？狀態(tài)是保存的信息狀態(tài)要有利于答案的求解狀態(tài)要容易轉(zhuǎn)移一個(gè)簡(jiǎn)單的例子，dp[n]=dp[n-1]+dp[n-2]兩個(gè)條件？無(wú)后效性狀
2、態(tài)間的轉(zhuǎn)移與如何到達(dá)某狀態(tài)無(wú)關(guān)狀態(tài)定義完整而唯一最優(yōu)子結(jié)構(gòu)當(dāng)前狀態(tài)可以從之前的某個(gè)或某些狀態(tài)直接得到狀態(tài)轉(zhuǎn)移包含了所有的可能復(fù)雜度？時(shí)間復(fù)雜度：狀態(tài)數(shù)*狀態(tài)轉(zhuǎn)移數(shù)空間復(fù)雜度：狀態(tài)數(shù)？例題所有代碼僅做演示，肯定是過(guò)不了題的。（雖然專題好像沒(méi)有例題）例題1：數(shù)字三角形311276645827341從上往下走，每次可以向左下或右下走一個(gè)，直到最下行，問(wèn)經(jīng)過(guò)數(shù)字的和最大是多少？例題1：數(shù)字三角形311276645827341貪心？在第二行就迷失了方向例題1：數(shù)字三角形311276645827341定義狀態(tài)dp[i][
3、j]表示當(dāng)走到第i行，第j個(gè)節(jié)點(diǎn)，能夠得到的最大的和。Ans=max{dp[5][k]},k=1...5例題1：數(shù)字三角形311276645827341狀態(tài)轉(zhuǎn)移:dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+val[i][j]dp[i][j]表示當(dāng)走到第i行，第j個(gè)節(jié)點(diǎn)，能夠得到的最大的和。例題1：數(shù)字三角形311276645827341狀態(tài)轉(zhuǎn)移:dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+val[i][j]dp[i][j]表示當(dāng)走到第i行，第j個(gè)
4、節(jié)點(diǎn)，能夠得到的最大的和。例題1：數(shù)字三角形自頂而下(記憶化搜索)dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+val[i][j]例題1：數(shù)字三角形自底而上(遞推)dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+val[i][j]例題2：最長(zhǎng)上升子序列給定一個(gè)長(zhǎng)度為n(1<=n<=1000)的整數(shù)序列a[i]，求它的一個(gè)子序列(子序列即在原序列任意位置刪除0或多個(gè)元素后的序列)，滿足如下條件：1、該序列單調(diào)遞增；2、在所有滿足條件1的序列中長(zhǎng)度是最長(zhǎng)的
5、；例題2：最長(zhǎng)上升子序列給定一個(gè)長(zhǎng)度為n(1<=n<=1000)的整數(shù)序列a[i]，求它的一個(gè)子序列(子序列即在原序列任意位置刪除0或多個(gè)元素后的序列)，滿足如下條件：1、該序列單調(diào)遞增；2、在所有滿足條件1的序列中長(zhǎng)度是最長(zhǎng)的；狀態(tài)定義：dp[i]表示以第i個(gè)數(shù)結(jié)尾的上升子序列最長(zhǎng)的長(zhǎng)度。狀態(tài)轉(zhuǎn)移：dp[i]=max{dp[j]}+1其中j=1….i-1,且a[i]>a[j]Ans=max{dp[i]},i=1...n時(shí)間復(fù)雜度：O(n2)空間復(fù)雜度：O(n)例題2：最長(zhǎng)上升子序列演示代碼例題3：區(qū)間dp（
6、POJ3280）給定一個(gè)長(zhǎng)度為n（n<=1000）的字符串A，求插入最少多少個(gè)字符使得它變成一個(gè)回文串。例題3：區(qū)間dp狀態(tài)定義：dp[i][j]表示A[i...j]成為回文串需要插入的字符數(shù)。注意i>j時(shí)表示空串，是回文串，是有意義的。狀態(tài)轉(zhuǎn)移：A[i]==A[j]時(shí)，dp[i][j]=dp[i+1][j-1]A[i]!=A[j]時(shí)，我們既可以在A[i]后插入一個(gè)A[j]，也可以在A[j]前插入一個(gè)A[i]，因此有dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1Ans=dp[1][
7、len]給定一個(gè)長(zhǎng)度為n（n<=1000）的字符串A，求插入最少多少個(gè)字符使得它變成一個(gè)回文串。例題3：區(qū)間dp演示代碼例題4：狀壓dp（TSP）對(duì)于一個(gè)節(jié)點(diǎn)數(shù)<=15的圖，要求找到一條路徑能夠遍歷每一個(gè)節(jié)點(diǎn)一次后返回出發(fā)點(diǎn)(Hamiltonianpath)，并且路徑距離最短。例題4：狀壓dp直接枚舉所有可能的順序，O(n!)無(wú)法承受。狀態(tài)定義：//注意這題從0開(kāi)始計(jì)數(shù)memo[i][j]i的每一位表示已經(jīng)經(jīng)過(guò)的點(diǎn)，j表示當(dāng)前所在的點(diǎn)由于狀態(tài)轉(zhuǎn)移沒(méi)有明顯的順序，用記憶化搜索比較好。search(i,j):fo
8、rkinnotvisitednode:search(i
9、(1<
