動(dòng)態(tài)規(guī)劃講義

1、動(dòng)態(tài)規(guī)劃(Dynamic Programming)-QWZeng問(wèn)題一： 有n堆不同的沙，標(biāo)號(hào)從1到n，第i堆沙的單位價(jià)值為Vi，總重量為Wi。現(xiàn)有一個(gè)袋子，最多能承受G重量的上限，求能裝入沙的最大價(jià)值是多少？問(wèn)題二： 有n個(gè)物品，標(biāo)號(hào)從1到n，第i個(gè)物品的價(jià)值為Vi，重量為Wi。現(xiàn)有一個(gè)袋子，最多能承受G重量的上限，求能裝入物品的最大價(jià)值是多少？（物品不能拆分）solution問(wèn)題三： 一個(gè)括號(hào)序列，只包含 ( , ) , , 四種括號(hào)，我們定義一個(gè)規(guī)范括號(hào)序列，一個(gè)規(guī)范括號(hào)序列滿(mǎn)足以下條件：a. 一個(gè)空串是規(guī)范的b. 如果s是一個(gè)規(guī)范括號(hào)序列，那么(s) 和 s 也是規(guī)范的c. 如果a和b

2、是規(guī)范的，那么ab也是規(guī)范的d. 除以上情況外，都是不規(guī)范的 給一個(gè)括號(hào)序列（長(zhǎng)度 =200)，問(wèn)其最長(zhǎng)的規(guī)范子序列是多長(zhǎng) ？ solutionDP的重要性：的重要性： a. DP占據(jù)了15%的比重 b. DP覆蓋面很廣，能跟各種問(wèn)題結(jié)合起來(lái)考查 c. 分析問(wèn)題的一種基本的有用的思維方式動(dòng)態(tài)規(guī)劃的基本原理動(dòng)態(tài)規(guī)劃的基本原理l最優(yōu)性原理作為整個(gè)過(guò)程的最優(yōu)策略，它滿(mǎn)足：相對(duì)前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。l無(wú)后效性原則給定某一階段的狀態(tài)，則在這一階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時(shí)，整個(gè)過(guò)程也就確定了。這個(gè)性質(zhì)意味著過(guò)程的歷史只能通過(guò)當(dāng)前

3、的狀態(tài)去影響它的未來(lái)的發(fā)展，這個(gè)性質(zhì)稱(chēng)為無(wú)后效性。動(dòng)態(tài)規(guī)劃的基本步奏：動(dòng)態(tài)規(guī)劃的基本步奏：一： 建立狀態(tài)表示二： 寫(xiě)出狀態(tài)轉(zhuǎn)移方程三： 實(shí)現(xiàn)(包括一些空間優(yōu)化，時(shí)間優(yōu)化）例子一： 爬樓梯 小Q要爬樓梯，他一次可以爬一層，也可以爬兩層，問(wèn)小Q爬n層樓層有多少種方式。 樣例： 輸入： 4輸出： 5 狀態(tài)：dpi 表示爬i層樓梯有dpi種方式狀態(tài)轉(zhuǎn)移方程： dpi = dpi-1 + dpi-2實(shí)現(xiàn)： dp0 = dp1 = 1;for(int i=2; i=n; i+) dpi = dpi-1 + dpi-2;dpn 即為答案引例二： 狀態(tài)： dp i j 表示前i個(gè)物品總重量不超過(guò)j時(shí)可以裝的最

4、大的價(jià)值 狀態(tài)轉(zhuǎn)移方程：dp i j = max ( dpi-1j, dpi-1 j-wi + vi ) 實(shí)現(xiàn)： dp00 = 0;for(int i=1; i=n; i+) for(int j=0; j=wi) dpij = max(dpij, dpi-1j-wi + vi); dpnG 即為答案int p=0; dpp0 = 0;for(int i=1; i=n; i+) for(int j=0; j=wi) dp1-pj = max(dp1-pj, dppj-wi+vi); p = 1-p;dppG 即為答案for(int i=1; i=wi; j-) dpj = max(dpj, dp

5、j-wi+vi);dpG 即為答案引例三： 狀態(tài)： dp i j 表示串s(ij) 內(nèi)最長(zhǎng)的規(guī)范子序列 狀態(tài)轉(zhuǎn)移： dpij = max if(si, sk 配對(duì)) dpi+1k-1 + dpk+1j + 2;dpi+1 j ; 實(shí)現(xiàn)： bool match(int i, int j) if(si=(&sj=) | si=&sj=) return true; return false;memset(dp, -1, sizeof(dp);int dfs(int i, int j) if(i=j) return 0; if(dpij=0) return dpij; for(int

6、k=i+1; k=j; k+) if(match(i,k) dpij = max(dpij, dfs(i+1, k-1) + dfs(k+1, j) + 2); dpij = max(dpij, dfs(i+1, j); return dpij;引例三實(shí)現(xiàn)：實(shí)現(xiàn)上的技巧：實(shí)現(xiàn)上的技巧：一. 順推二. 雙向dp三. 空間優(yōu)化順推順推用隊(duì)列存儲(chǔ)有效狀態(tài)例比如：奇怪的電梯 有一個(gè)n層的電梯,在第i層，只能選擇上ki層，或下ki層，問(wèn)從A層到B層，最少的操作次數(shù)是多少？若無(wú)法到達(dá)，輸出-1 狀態(tài)：dp i 表示達(dá)到第i層所需的最少的操作次數(shù)狀態(tài)轉(zhuǎn)移方程： 逆推：dp i = min dp j + 1

7、, 對(duì)所有滿(mǎn)足 j +kj = i 或 j-kj = i 的j 順推：dp i + ki = min ( dp i + ki , dpi + 1); dp i - ki = min ( dp i - ki , dpi + 1);實(shí)現(xiàn)： 奇怪的電梯奇怪的電梯直接實(shí)現(xiàn)：memset(dp, 0 x3f, sizeof(dp);dpA = 0;while(true) bool flag = false; for(int i=1; i=n; i+) if(dpiinf) if(i+kidpi+1) dpi+ki = dpi + 1; flag = true; if(i-ki0 & dpi-ki

8、dpi+1) dpi-ki = dpi + 1; flag = true; if(!flag) break;用隊(duì)列存儲(chǔ)有效狀態(tài)：int quemaxn, head=0, tail=0;memset(dp, 0 x3f, sizeof(dp);dpA = 0;quetail+ = A;while(tailhead) int i = quehead+; if(i+kidpi+1) dpi+ki = dpi + 1; quetail+ = i + ki; if(i-ki0 & dpi-kidpi+1) dpi-ki = dpi + 1; quetail+ = i - ki; 從狀態(tài)轉(zhuǎn)移方程中

9、考慮一些優(yōu)化策略：從狀態(tài)轉(zhuǎn)移方程中考慮一些優(yōu)化策略：a. 若決策涉及到區(qū)間操作，可考慮用線(xiàn)段樹(shù)或數(shù)組數(shù)組來(lái)優(yōu)化b. 若存在單調(diào)性，可利用其進(jìn)行優(yōu)化(如四邊形定理，單調(diào)隊(duì)列)例題：石子合并 有n堆石子排成一條直線(xiàn)，標(biāo)號(hào)從1到n。第i堆石子有ai個(gè)，現(xiàn)對(duì)這n堆石子進(jìn)行合并，每次合并只能選取相鄰的兩堆，合并的代價(jià)這這兩堆石子的總個(gè)數(shù)。問(wèn)將這n堆石子合并為一堆所需的最小的代價(jià)。樣例： 輸入 輸出33 5 6 22dpij 表示將第i堆到第j堆直接所有石子合并為一堆所需的最小代價(jià)wij 表示從第i堆到第j堆之間的總的石子數(shù)dpij = min dpik + dpk+1j + wij , k=i &

10、; kj時(shí)間復(fù)雜度 o(n3) 令sij 為dpij 的最優(yōu)決策則有單調(diào)性 si-1j = sij = sij+1時(shí)間復(fù)雜度 o(n2)建立狀態(tài)的一個(gè)重要思想：建立狀態(tài)的一個(gè)重要思想：在變與不變中建立狀態(tài)在變與不變中建立狀態(tài)例題：撲克牌 每張撲克牌由兩個(gè)字符表示，第一個(gè)表示它的值，第二個(gè)表示其花色，值包括以下字符：2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K, A.花色包括以下四種字符：S, D, H, C. 現(xiàn)有n張撲克牌，將它們從左到右排成一排。即初始時(shí)刻有n堆撲克牌，每堆一張。假設(shè)現(xiàn)在又x堆撲克牌，每次操作為：將第x堆疊放到第x-1堆或第x-3堆，在它們存在的情況

11、下，并且第x堆和要疊放的那一堆堆頂?shù)膿淇伺埔粗迪嗤?，要么花色相同，滿(mǎn)足這個(gè)條件才能疊放。 問(wèn)能放將這n堆撲克牌疊成一堆。 輸入：第一行n (1= n =52) 為撲克牌數(shù)量，接下來(lái)一行為n張撲克牌的信息 輸出：如果可以疊成一堆輸出YES，否則輸出NOdp p i j k 表示還剩p堆時(shí)，第p堆堆頂為第i張撲克牌，第p-1堆堆頂為第j張撲克牌，第p-2堆堆頂為第k張撲克牌#define maxn 54bool dpmaxnmaxnmaxnmaxn;int n;char amaxn3;bool ok(int x, int y) return ax0=ay0 | ax1=ay1;bool dfs(

12、int p, int i, int j, int k) if(dppijk) return 0; if(p=3) return ok(i,j) & ok(i,k); if(ok(i,j)&dfs(p-1,i,k,p-3) return 1; if(ok(i,p-3)&dfs(p-1,j,k,i) return 1; dppijk = 1; return 0;int main() scanf(%d, &n); for(int i=1; i=n; i+) scanf(%s, a+i); if(n=1)|(n=2&ok(1,2)|dfs(n,n,n-1,n-2) printf(YESn); else pri