偉大的acm大神谷哥教我學(xué)算法.

引例

斐波那契數(shù)

定義一個(gè)函數(shù)，f(x) = f(x-1) + f(x-2)，x為正整數(shù)，定義f(1) = 1，f(2) = 1。給出整數(shù)n，求f(n)的數(shù)值。
直觀的做法：

int f(int n)
{
    if(n==1||n==2)
        return 1;
    return f(n-1)+f(n-2);
}

思考:如果n為10^7程序還可以運(yùn)行下去嗎？（這里不考慮數(shù)據(jù)會(huì)爆int的問(wèn)題）
顯然效率低下.如下圖所示:

beibo

我們可以看到計(jì)算f(n)的過(guò)程中有很多重復(fù)的計(jì)算。
這種做法的復(fù)雜度是指數(shù)級(jí)增長(zhǎng)的！
進(jìn)行優(yōu)化,保存子狀態(tài)，避免重復(fù)計(jì)算.

int f(int n){
    vector<int>F(n+1,0);
    F[1]=F[2]=1;
    for(int i=3;i<n;i++){
        F[i]=F[i-1]+F[i-2];
    }
    return F[n];
}

背包問(wèn)題

有n個(gè)價(jià)值和體積分別為wi和vi的物品。從這些物品中挑選出總體積不超過(guò)V的物品，求所有方案中價(jià)值總和的最大值。
條件：
1≤ n ≤ 100
1≤ wi，vi ≤ 100
1 ≤ V ≤ 10000
wi，vi, V 均為整數(shù)

首先想到的是樸素遞歸:

rec(0,v)
int rec(int index,int capacity){
    if(index==n) return 0;
    else if(capacity<v[index]){
        return rec(index+1,capacity);
    }
    else{
        return max(rec(index+1,capacity),
                   rec(index+1,capacity-v[index])+w[index])
    }
}

思考:深搜的深度是n每一次搜索需要兩個(gè)分支時(shí)間復(fù)雜度是O（2^n）n很大了之后怎么辦？
來(lái)看一下rec函數(shù)的遞歸計(jì)算情況
例如:n=4,(w,v)={(3,2),(2,1),(4,3),(2,2)},V=5

rec

以上問(wèn)題都存在著冗余重復(fù)的計(jì)算,每個(gè)都能劃分成子問(wèn)題解決.

DP

思想及概念

基本思想：一般求解最優(yōu)化問(wèn)題。將求解問(wèn)題分解成若干個(gè)子問(wèn)題，保存已解決的子問(wèn)題的答案，在需要的時(shí)候直接利用。

特點(diǎn)：子問(wèn)題重疊
子問(wèn)題的重疊能更好地顯示出動(dòng)態(tài)規(guī)劃的優(yōu)勢(shì)。因此可以打表記錄子問(wèn)題的答案。

性質(zhì)：

• 最優(yōu)子結(jié)構(gòu)：一個(gè)最優(yōu)策略的子策略也是最優(yōu)的。
• 無(wú)后效性：過(guò)去的步驟只能通過(guò)當(dāng)前的狀態(tài)影響未來(lái)的發(fā)展，當(dāng)前狀態(tài)是歷史的總結(jié)。

動(dòng)態(tài)規(guī)劃不是一種算法，而是一種思想，應(yīng)用于有動(dòng)態(tài)決策的問(wèn)題當(dāng)中。
動(dòng)態(tài)規(guī)劃的狀態(tài)是人為定義的。
一般步驟：

• 通過(guò)窮舉計(jì)算過(guò)程圖確定問(wèn)題狀態(tài)
• 列出狀態(tài)轉(zhuǎn)移方程（決策）
• 初始化和邊界條件
• 優(yōu)化

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

問(wèn)題描述:給定兩個(gè)字符串S，T(長(zhǎng)度小于1000)。求出這兩個(gè)字符串最長(zhǎng)的公共子序列的長(zhǎng)度。
思考舉例:

lcs

對(duì)于X和Y，我們?cè)囍?jì)算X[1:i]與Y[1:j]的最長(zhǎng)公共子序列。

lcs2

因此， 我們可以得到遞推方程：

lcs3

dp[i][j]為序列 (X1, X2, …, Xi)和 (Y1, Y2, …, Yj)的最長(zhǎng)公共子序列的長(zhǎng)度。

LIS(最長(zhǎng)上升子序列)

給出一個(gè)由n個(gè)數(shù)字成的序列A[1:n]，找出它的最長(zhǎng)單調(diào)上升子序列。即求最大的m

使得a1<a2<…<am且A[a1]<A[a2]<…<A[am]

思考：先舉出個(gè)例子 A[1:9] = 2 1 5 3 6 4 8 9 7。我們首先考慮A[1:i]的LIS，
令A(yù)[1:i]的LIS為dp[i].比如i=6,這時(shí)候A[i] = 4, 我們往i左邊看。

lis

從上邊的規(guī)律我們可以寫(xiě)出狀態(tài)轉(zhuǎn)移方程：

lis2

思考:這個(gè)算法的復(fù)雜度為O(N^2),還能做的更快嗎?

對(duì)于這個(gè)例子 A[1:9] = 2 1 5 3 6 4 8 9 7
當(dāng)i=6時(shí)，我們已經(jīng)算出dp[3] = dp[4] = 2
其中j = 3,對(duì)應(yīng)的序列為 {1, 5}
j = 4，對(duì)應(yīng)的序列為 {1, 3}
其實(shí)我們更傾向要{1, 3},因?yàn)閷?duì)于dp值為 2的情況A[j]越小,越有潛力被利用上進(jìn)行更新。
因此我們重新開(kāi)一個(gè)數(shù)組g,保存dp值為k的對(duì)應(yīng)的數(shù)組A中的最小值。因此當(dāng)i=6時(shí),
g數(shù)組中有兩個(gè)值,即g[1]=1,g[2]=3。
在計(jì)算dp[6]的時(shí)候只要用g數(shù)組中的值更新就好。

數(shù)組g，保存dp值為k的對(duì)應(yīng)的數(shù)組A中的最小值。
g[1]<=g[2]<=……<=g[k]
計(jì)算dp[i]: 在g中找到大于等于A[i]的第一個(gè)數(shù)j, 則dp[i] = j更新g: 由于g[j]>A[i],則需要更新g[j] = A[i].

file(g,g+n,INFINITY);
for(int i=0;i<n;i++){
    int j=lower_bound(g,g+n,A[i])-g;
    dp[i]=j+1;
    g[j]=A[i];
}

由于g是有序的，查找利用二分查找?？傮w復(fù)雜度為 O(n logn)

背包問(wèn)題0/1

有n個(gè)價(jià)值和體積分別為wi和vi的物品。從這些物品中挑選出總體積不超過(guò)V的物品，求所有方案中價(jià)值總和的最大值。

條件：
1≤ n ≤ 100
1≤ wi，vi ≤ 100
1 ≤ V ≤ 10000
wi，vi, V 均為整數(shù)

觀察這個(gè)題目的特點(diǎn)：

• V不超過(guò)10000
• 整數(shù)

引例中樸素方法有很多重復(fù)計(jì)算。
引例中的狀態(tài)是2維的(前index個(gè)背包，剩下容積)
引入dp[i][j]，表示前i個(gè)物品中用了容積j獲得的最大價(jià)值。

遞歸方程為:

beibao01

復(fù)雜度為O(n*V)

總結(jié)

動(dòng)態(tài)規(guī)劃是一種思想。動(dòng)態(tài)規(guī)劃有很多類型（如普通DP, 樹(shù)形DP，狀壓DP，按位DP，插頭DP等）；

動(dòng)態(tài)規(guī)劃思想的養(yǎng)成不可能一蹴而就，而是慢慢養(yǎng)成的。養(yǎng)成的過(guò)程需要不斷增加題目的見(jiàn)識(shí)面，不能局限于幾種類型的DP；

學(xué)好DP需要下很大功夫。同樣的, 學(xué)好DP，會(huì)對(duì)個(gè)人算法素養(yǎng)提升很大。而且，DP也是面試中常見(jiàn)的考點(diǎn)

參考:
《算法競(jìng)賽入門(mén)經(jīng)典》…………劉汝佳 等
《ACM競(jìng)賽基礎(chǔ)教程》………...俞經(jīng)善 等
《編程之法》……………………July
http://blog.csdn.net/zsc09_leaf/article/details/6536802
http://poj.org/problem?id=1458
http://poj.org/problem?id=3254
http://blog.csdn.net/y990041769/article/details/24658419