前言

作為一個(gè)退役狗跟大家扯這些東西，感覺確實(shí)有點(diǎn)。。。但是，針對(duì)網(wǎng)上沒有一篇文章能夠很詳細(xì)的把動(dòng)態(tài)規(guī)劃問(wèn)題說(shuō)明的很清楚，我決定還是拿出我的全部家當(dāng)，來(lái)跟大家分享我對(duì)動(dòng)態(tài)規(guī)劃的理解，我會(huì)盡可能的把所遇到的動(dòng)態(tài)規(guī)劃的問(wèn)題都涵蓋進(jìn)去，博主退役多年，可能有些地方會(huì)講的不完善，還望大家多多貢獻(xiàn)出自己的寶貴建議，共同進(jìn)步~~~

概念

首先我們得知道動(dòng)態(tài)規(guī)劃是什么東東，百度百科上是這么說(shuō)的，動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程(decision process)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過(guò)程(multistep decision process)的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過(guò)程優(yōu)化問(wèn)題的新方法——?jiǎng)討B(tài)規(guī)劃。1957年出版了他的名著《Dynamic Programming》，這是該領(lǐng)域的第一本著作。

小伙伴們估計(jì)看到這段話都已經(jīng)蒙圈了吧，那么動(dòng)態(tài)規(guī)劃到底是什么呢？這么說(shuō)吧，動(dòng)態(tài)規(guī)劃就是一種通過(guò)把原問(wèn)題分解為相對(duì)簡(jiǎn)單的子問(wèn)題的方式求解復(fù)雜問(wèn)題的方法。動(dòng)態(tài)規(guī)劃常常適用于有重疊子問(wèn)題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問(wèn)題。

舉個(gè)例子，我們都是從學(xué)生時(shí)代過(guò)來(lái)的人，學(xué)生時(shí)代我們最喜歡的一件事是什么呢？就是等待寒暑假的到來(lái)，因?yàn)榭梢苑偶倭税-^，嘻嘻，誰(shuí)會(huì)不喜歡玩呢~~可是呢，放假之前我們必須經(jīng)歷的一個(gè)過(guò)程就是期末考試，期末沒考好，回家肯定是要挨板子的，所以我們就需要去復(fù)習(xí)啦，而在復(fù)習(xí)過(guò)程中我們是不是要去熟記書中的每一個(gè)知識(shí)點(diǎn)呢，書是一個(gè)主體，考試都是圍繞著書本出題，所以我們很容易知道書本不是核心，書本中的若干個(gè)知識(shí)點(diǎn)才是核心，然后那個(gè)若干個(gè)知識(shí)點(diǎn)又可以拆解成無(wú)數(shù)個(gè)小知識(shí)點(diǎn)，是不是發(fā)現(xiàn)有點(diǎn)像一棵倒立的樹呢，但是呢，當(dāng)我們要運(yùn)用這些知識(shí)點(diǎn)去解題時(shí)，每一道題所涉及的知識(shí)點(diǎn)，其實(shí)就是這些知識(shí)點(diǎn)的一個(gè)排列組合的所有可能結(jié)果的其中一種組合方式，這個(gè)能理解的了嘛？

對(duì)這個(gè)排列組合，我們舉個(gè)例子，比如小明爸爸叫小明去買一包5元錢的香煙，他給了一張5元的，三張2元的，五張1元的紙幣，問(wèn)小明有幾種付錢的方式？這個(gè)選擇方式我們很容易就知道，我們可以對(duì)這些可能結(jié)果進(jìn)行一個(gè)枚舉。

這個(gè)組合方式有很多種，我們可以對(duì)其進(jìn)行一個(gè)分類操作：

當(dāng)我們只用一張紙幣的時(shí)候：一張5元紙幣

當(dāng)我們需要用兩張紙幣的時(shí)候：結(jié)果不存在

當(dāng)我們需要用三張紙幣的時(shí)候：兩張2元紙幣和一張1元紙幣

當(dāng)我們需要用四張紙幣的時(shí)候：一張2元紙幣，三張一元紙幣

當(dāng)我們需要用五張紙幣的時(shí)候：五張一元紙幣

從上面的分類分析來(lái)看，我們知道，排列組合的方式共有四種，而我如果問(wèn)你，我現(xiàn)在需要花費(fèi)的紙幣張數(shù)要最小，我們應(yīng)該選取哪種方式呢，很顯然我們直接選取第一種方法，使用一張5元的紙幣就好了啊，這個(gè)就是求最優(yōu)解的問(wèn)題啦，也就是我們今天需要研究的問(wèn)題，動(dòng)態(tài)規(guī)劃問(wèn)題

相信大家到了這里，對(duì)動(dòng)態(tài)規(guī)劃應(yīng)該有了初步的認(rèn)識(shí)吧，我也很高興帶大家一起暢游算法的美妙，那么請(qǐng)繼續(xù)聽我吹牛皮吧，啦啦啦~~~

基本思想

若要解一個(gè)給定問(wèn)題，我們需要解其不同部分（即子問(wèn)題），再合并子問(wèn)題的解以得出原問(wèn)題的解。 通常許多子問(wèn)題非常相似，為此動(dòng)態(tài)規(guī)劃法試圖僅僅解決每個(gè)子問(wèn)題一次，從而減少計(jì)算量： 一旦某個(gè)給定子問(wèn)題的解已經(jīng)算出，則將其記憶化存儲(chǔ)，以便下次需要同一個(gè)子問(wèn)題解之時(shí)直接查表。 這種做法在重復(fù)子問(wèn)題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長(zhǎng)時(shí)特別有用。

簡(jiǎn)單來(lái)說(shuō)，還是拿上面的例子來(lái)講，比如說(shuō)你做一道數(shù)學(xué)難題，難題，無(wú)非就是很難嘛，但是我們需要做的就是把這道難題解出來(lái)，對(duì)于一個(gè)數(shù)學(xué)水平很菜的選手來(lái)講，做出一道難題是不是會(huì)感覺非常困難呢？其實(shí)換個(gè)角度來(lái)看待這個(gè)問(wèn)題，一道難題其實(shí)是由若干個(gè)子問(wèn)題構(gòu)成，而每一個(gè)子問(wèn)題也許會(huì)是一些很基礎(chǔ)的問(wèn)題，一個(gè)入門級(jí)的問(wèn)題，類似于像1+1=2這樣的問(wèn)題，相信大家只要有所接觸都能熟練掌握，而針對(duì)這些難題，我們也應(yīng)該去考慮把它進(jìn)行一個(gè)分解，我現(xiàn)在腦邊還能回憶起中學(xué)老師說(shuō)過(guò)的話，做不來(lái)的題目你可以把一些解題過(guò)程先寫出來(lái)，把最基本的思路寫出來(lái)，寫著寫著說(shuō)不定答案就出來(lái)了呢？相信看完我這篇文章的人水平都能再上一個(gè)臺(tái)階，不僅如此，對(duì)于當(dāng)前的全球熱潮Artificial Intelligence也是如此，看似非常復(fù)雜繁瑣的算法，把它進(jìn)行一個(gè)拆解，其實(shí)就是若干個(gè)數(shù)學(xué)公式的組合，最根本的來(lái)源還是基礎(chǔ)數(shù)學(xué)，所以啊，學(xué)好數(shù)學(xué)，未來(lái)是光明的~~~

分治與動(dòng)態(tài)規(guī)劃

共同點(diǎn)：二者都要求原問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì),都是將原問(wèn)題分而治之,分解成若干個(gè)規(guī)模較小(小到很容易解決的程序)的子問(wèn)題.然后將子問(wèn)題的解合并,形成原問(wèn)題的解.

不同點(diǎn)：分治法將分解后的子問(wèn)題看成相互獨(dú)立的，通過(guò)用遞歸來(lái)做。

　　　　?動(dòng)態(tài)規(guī)劃將分解后的子問(wèn)題理解為相互間有聯(lián)系,有重疊部分，需要記憶，通常用迭代來(lái)做。

問(wèn)題特征

最優(yōu)子結(jié)構(gòu)：當(dāng)問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解時(shí)，稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

重疊子問(wèn)題：在用遞歸算法自頂向下解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用了這種子問(wèn)題的重疊性質(zhì)，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，在以后盡可能多地利用這些子問(wèn)題的解。

我認(rèn)為可能會(huì)和回溯的部分問(wèn)題有點(diǎn)類似，有興趣的同學(xué)可以自行閱讀一下我曾經(jīng)寫過(guò)的文章回溯算法入門及經(jīng)典案例剖析(初學(xué)者必備寶典)

解題步驟

1.找出最優(yōu)解的性質(zhì)，刻畫其結(jié)構(gòu)特征和最優(yōu)子結(jié)構(gòu)特征，將原問(wèn)題分解成若干個(gè)子問(wèn)題；

　　把原問(wèn)題分解為若干個(gè)子問(wèn)題，子問(wèn)題和原問(wèn)題形式相同或類似，只不過(guò)規(guī)模變小了。子問(wèn)題都解決，原問(wèn)題即解決，子問(wèn)題的解一旦求出就會(huì)被保存，所以每個(gè)子問(wèn)題只需求解一次。

2.遞歸地定義最優(yōu)值，刻畫原問(wèn)題解與子問(wèn)題解間的關(guān)系，確定狀態(tài)；

　　在用動(dòng)態(tài)規(guī)劃解題時(shí)，我們往往將和子問(wèn)題相關(guān)的各個(gè)變量的一組取值，稱之為一個(gè)“狀態(tài)”。一個(gè)“狀態(tài)”對(duì)應(yīng)于一個(gè)或多個(gè)子問(wèn)題， 所謂某個(gè)“狀態(tài)”下的“值”，就是這個(gè)“狀 態(tài)”所對(duì)應(yīng)的子問(wèn)題的解。所有“狀態(tài)”的集合，構(gòu)成問(wèn)題的“狀態(tài)空間”。“狀態(tài)空間”的大小，與用動(dòng)態(tài)規(guī)劃解決問(wèn)題的時(shí)間復(fù)雜度直接相關(guān)。

3.以自底向上的方式計(jì)算出各個(gè)子問(wèn)題、原問(wèn)題的最優(yōu)值，并避免子問(wèn)題的重復(fù)計(jì)算；

　　定義出什么是“狀態(tài)”，以及在該“狀態(tài)”下的“值”后，就要找出不同的狀態(tài)之間如何遷移――即如何從一個(gè)或多個(gè)“值”已知的 “狀態(tài)”，求出另一個(gè)“狀態(tài)”的“值”(遞推型)。

4.根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解，確定轉(zhuǎn)移方程;

　　狀態(tài)的遷移可以用遞推公式表示，此遞推公式也可被稱作“狀態(tài)轉(zhuǎn)移方程”。

實(shí)例分析

1.01背包問(wèn)題

有N件物品和一個(gè)容量為V的背包。第i件物品的費(fèi)用是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過(guò)背包容量，且價(jià)值總和最大。?

f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。

將前i件物品放入容量為v的背包中”這個(gè)子問(wèn)題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i-1件物品的問(wèn)題。如果不放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”；如果放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是f [i-1][v-c[i]]再加上通過(guò)放入第i件物品獲得的價(jià)值w[i]。

對(duì)01背包不清楚的或者有興趣閱讀的同學(xué)請(qǐng)移步至這里

下面貼下01背包的模板

void backtrack(int i,int cp,int cw) {if(i>n){if(cp>bestp){bestp=cp;for(i=1;i<=n;i++) bestx[i]=x[i];}}else{for(int j=0;j<=1;j++) {x[i]=j;if(cw+x[i]*w[i]<=c) {cw+=w[i]*x[i];cp+=p[i]*x[i];backtrack(i+1,cp,cw);cw-=w[i]*x[i];cp-=p[i]*x[i];}}} }

最終我們可以去得到答案：

int n,c,bestp;//物品個(gè)數(shù),背包容量,最大價(jià)值 int p[10000],w[10000],x[10000],bestx[10000];//物品的價(jià)值,物品的重量,物品的選中情況 int main() {bestp=0; cin>>c>>n;for(int i=1;i<=n;i++) cin>>w[i];for(int i=1;i<=n;i++) cin>>p[i];backtrack(1,0,0);cout<<bestp<<endl; }

2.矩陣連乘

給定n個(gè)可連乘的矩陣{A1, A2, …,An}，根據(jù)矩陣乘法結(jié)合律，可有多種不同計(jì)算次序，每種次序有不同的計(jì)算代價(jià)，也就是數(shù)乘次數(shù)。例如給定2個(gè)矩陣A[pi,pj]和B[pj,pk]，A×B為[pi,pk]矩陣，數(shù)乘次數(shù)為pi×pj×pk。將矩陣連乘積Ai…Aj簡(jiǎn)記為A[i:j] ，這里i≤j。考察計(jì)算A[i:j]的最優(yōu)計(jì)算次序，設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i≤k<j，則A[i:j]的計(jì)算量=A[i:k]的計(jì)算量+A[k+1:j]的計(jì)算量+A[i:k]和A[k+1:j]相乘的計(jì)算量。計(jì)算A[i:j]的最優(yōu)次序所包含的計(jì)算矩陣子鏈A[i:k]和A[k+1:j]的次序也是最優(yōu)的。即矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解，這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)，問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。

舉個(gè)例子：

給出N個(gè)數(shù)，每次從中抽出一個(gè)數(shù)(第一和最后一個(gè)不能抽)，該次的得分即為抽出的數(shù)與相鄰兩個(gè)數(shù)的乘積。一直這樣將每次的得分累加直到只剩下首尾兩個(gè)數(shù)為止，問(wèn)最小得分。

實(shí)現(xiàn)過(guò)程如下：

#define maxn 105 int dp[maxn][maxn],a[maxn]; int main() {int n;cin>>n;int i,j,k,len;memset(dp,0,sizeof(dp)); //len是設(shè)置步長(zhǎng),也就是j減i的值 for(i=0;i<n;i++) cin>>a[i];for(i=0;i<n-2;i++) dp[i][i+2]=a[i]*a[i+1]*a[i+2];//如果只有三個(gè)數(shù)就直接乘起來(lái) for(len=3;len<n;len++){for(i=0;i+len<n;i++){ j=i+len;for(k=i+1;k<j;k++){if(dp[i][j]==0) dp[i][j]=dp[i][k]+dp[k][j]+a[i]*a[k]*a[j];else dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]);}}}cout<<dp[0][n-1]<<endl;return 0; }

3.最長(zhǎng)公共子序列與最長(zhǎng)公共子串

子串應(yīng)該比較好理解，至于什么是子序列，這里給出一個(gè)例子：有兩個(gè)母串

• cnblogs
• belong

比如序列bo, bg, lg在母串cnblogs與belong中都出現(xiàn)過(guò)并且出現(xiàn)順序與母串保持一致，我們將其稱為公共子序列。最長(zhǎng)公共子序列（Longest Common Subsequence, LCS），顧名思義，是指在所有的子序列中最長(zhǎng)的那一個(gè)。子串是要求更嚴(yán)格的一種子序列，要求在母串中連續(xù)地出現(xiàn)。在上述例子的中，最長(zhǎng)公共子序列為blog（cnblogs, belong），最長(zhǎng)公共子串為lo（cnblogs, belong）。

對(duì)于母串X=<x1,x2,?,xm>X=<x1,x2,?,xm>, Y=<y1,y2,?,yn>Y=<y1,y2,?,yn>，求LCS與最長(zhǎng)公共子串。

暴力解法：

假設(shè) m<nm<n， 對(duì)于母串XX，我們可以暴力找出2m2m個(gè)子序列，然后依次在母串YY中匹配，算法的時(shí)間復(fù)雜度會(huì)達(dá)到指數(shù)級(jí)O(n?2m)O(n?2m)。顯然，暴力求解不太適用于此類問(wèn)題。

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

假設(shè)Z=<z1,z2,?,zk>Z=<z1,z2,?,zk> 是XX 與YY 的LCS， 我們觀察到

• 如果xm=ynxm=yn ，則zk=xm=ynzk=xm=yn ，有Zk?1Zk?1 是Xm?1Xm?1 與Yn?1Yn?1 的LCS；
• 如果xm≠ynxm≠yn ，則ZkZk 是XmXm 與Yn?1Yn?1 的LCS，或者是Xm?1Xm?1 與YnYn 的LCS。

因此，求解LCS的問(wèn)題則變成遞歸求解的兩個(gè)子問(wèn)題。但是，上述的遞歸求解的辦法中，重復(fù)的子問(wèn)題多，效率低下。改進(jìn)的辦法——用空間換時(shí)間，用數(shù)組保存中間狀態(tài)，方便后面的計(jì)算。這就是動(dòng)態(tài)規(guī)劃（DP)的核心思想了。

DP求解LCS

用二維數(shù)組c[i][j]記錄串x1x2?xix1x2?xi與y1y2?yjy1y2?yj的LCS長(zhǎng)度，

用i，j遍歷兩個(gè)子串x,y，如果兩個(gè)元素相等就+1 ，不等就用上一個(gè)狀態(tài)最大的元素

實(shí)現(xiàn)過(guò)程如下：

int lcs(string str1, string str2, vector<vector<int>>& vec) {int len1 = str1.size();int len2 = str2.size();vector<vector<int>> c(len1 + 1, vector<int>(len2 + 1, 0));for (int i = 0; i <= len1; i++) {for (int j = 0; j <= len2; j++) {if (i == 0 || j == 0) {c[i][j] = 0;}else if (str1[i - 1] == str2[j - 1]) {c[i][j] = c[i - 1][j - 1] + 1;vec[i][j] = 0;}else if (c[i - 1][j] >= c[i][j - 1]){c[i][j] = c[i - 1][j];vec[i][j] = 1;}else{c[i][j] = c[i][j - 1];vec[i][j] = 2;}}}return c[len1][len2]; }void print_lcs(vector<vector<int>>& vec, string str, int i, int j) {if (i == 0 || j == 0){return;}if (vec[i][j] == 0){print_lcs(vec, str, i - 1, j - 1);printf("%c", str[i - 1]);}else if (vec[i][j] == 1){print_lcs(vec, str, i - 1, j);}else{print_lcs(vec, str, i, j - 1);} }int _tmain(int argc, _TCHAR* argv[]) {string str1 = "123456";string str2 = "2456";vector<vector<int>> vec(str1.size() + 1, vector<int>(str2.size() + 1, -1));int result = lcs(str1, str2, vec);cout << "result = " << result << endl;print_lcs(vec, str1, str1.size(), str2.size());getchar();return 0; }

DP求解最長(zhǎng)公共子串

前面提到了子串是一種特殊的子序列，因此同樣可以用DP來(lái)解決。定義數(shù)組的存儲(chǔ)含義對(duì)于后面推導(dǎo)轉(zhuǎn)移方程顯得尤為重要，糟糕的數(shù)組定義會(huì)導(dǎo)致異常繁雜的轉(zhuǎn)移方程。考慮到子串的連續(xù)性，將二維數(shù)組c[i,j]c[i,j]用來(lái)記錄具有這樣特點(diǎn)的子串——結(jié)尾為母串x1x2?xix1x2?xi與y1y2?yjy1y2?yj的結(jié)尾——的長(zhǎng)度。

區(qū)別就是因?yàn)槭沁B續(xù)的，如果兩個(gè)元素不等，那么就要=0了而不能用之前一個(gè)狀態(tài)的最大元素

最長(zhǎng)公共子串的長(zhǎng)度為 max(c[i,j]),?i∈{1,?,m},j∈{1,?,n}max(c[i,j]),?i∈{1,?,m},j∈{1,?,n}。

實(shí)現(xiàn)過(guò)程如下：

int lcs_2(string str1, string str2, vector<vector<int>>& vec) {int len1 = str1.size();int len2 = str2.size();int result = 0; //記錄最長(zhǎng)公共子串長(zhǎng)度vector<vector<int>> c(len1 + 1, vector<int>(len2 + 1, 0));for (int i = 0; i <= len1; i++) {for (int j = 0; j <= len2; j++) {if (i == 0 || j == 0) {c[i][j] = 0;}else if (str1[i - 1] == str2[j - 1]) {c[i][j] = c[i - 1][j - 1] + 1;vec[i][j] = 0;result = c[i][j] > result ? c[i][j] : result;}else {c[i][j] = 0;}}}return result; }void print_lcs(vector<vector<int>>& vec, string str, int i, int j) {if (i == 0 || j == 0){return;}if (vec[i][j] == 0){print_lcs(vec, str, i - 1, j - 1);printf("%c", str[i - 1]);}else if (vec[i][j] == 1){print_lcs(vec, str, i - 1, j);}else{print_lcs(vec, str, i, j - 1);} } int _tmain(int argc, _TCHAR* argv[]) {string str1 = "123456";string str2 = "14568";vector<vector<int>> vec(str1.size() + 1, vector<int>(str2.size() + 1, -1));int result = lcs_2(str1, str2, vec);cout << "result = " << result << endl;print_lcs(vec, str1, str1.size(), str2.size());getchar();return 0; }

4.走金字塔

給定一個(gè)由n行數(shù)字組成的數(shù)字三角型，如圖所示。設(shè)計(jì)一個(gè)算法，計(jì)算從三角形的頂至底的一條路徑，使該路徑經(jīng)過(guò)的數(shù)字總和最大。路徑上的每一步都只能往左下或右下走，給出這個(gè)最大和。
? ? ? ? 7?
? ? ? 3 ?8?
? ? 8 ?1 ?0?
? 2 ?7 ?4 ?4?
4 ?5 ?2 ?6 ?5

對(duì)于這種問(wèn)題，我們可以有正向和反向兩種思考方式。正向思考這個(gè)問(wèn)題，dp[i][j]表示從第一行第一列到第i行第j列最大的數(shù)字總和；反向思考這個(gè)問(wèn)題，dp[i][j]表示從第i行第j列到最后一行最大的數(shù)字總和。反向思考的代碼要簡(jiǎn)潔一些

正向思考：

int triangle[110][110],dp[110][110]; int main() {int N;cin>>N;memset(dp,0,sizeof(dp));memset(triangle,0,sizeof(triangle));for(int i=1;i<=N;i++){for(int j=1;j<=i;j++){cin>>triangle[i][j];}}dp[1][1]=triangle[1][1];for(int i=2;i<=N;i++){for(int j=1;j<=i;j++){if(j!=1) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+triangle[i][j]);if(j!=i) dp[i][j]=max(dp[i][j],dp[i-1][j]+triangle[i][j]);}}int max=-1;for(int i=1;i<=N;i++){if(dp[N][i]>max) max=dp[N][i];}cout<<max<<endl;return 0; }

反向思考：

int triangle[110][110],dp[110][110]; int main() {int N;cin>>N;memset(dp,0,sizeof(dp));memset(triangle,0,sizeof(triangle));for(int i=1;i<=N;i++){for(int j=1;j<=i;j++){cin>>triangle[i][j];}}for(int i=1;i<=N;i++){dp[N][i]=triangle[N][i];}for(int i=N-1;i>=1;i--){for(int j=1;j<=i;j++){dp[i][j]=max(dp[i+1][j]+triangle[i][j],dp[i+1][j+1]+triangle[i][j]);}}cout<<dp[1][1]<<endl;return 0; }

5.最長(zhǎng)遞增子序列(LIS)

最長(zhǎng)遞增子序列的定義和最長(zhǎng)公共子序列的定義差不多，只不過(guò)最長(zhǎng)遞增子序列是針對(duì)單個(gè)數(shù)組的。

舉個(gè)例子，給出一序列，求出該序列的最長(zhǎng)上升子序列的最大長(zhǎng)度。

我們可以這么考慮，用數(shù)組a[]存儲(chǔ)序列，b[i]表示以a[i]為結(jié)尾的序列的最大長(zhǎng)度。

因此要求出b[i]的最大值，即求出max{b[0],b[1]....b[i-1]}的最大值，那么b[i]的最大值為max{b[0],b[1]....b[i-1]}+1; 即可寫出狀態(tài)方程：b[i]=max{b[0],b[1].....b[j]}+1;(0<=j<i&&a[j]<a[i]),然后求出數(shù)組b[]中的最大值即為所求。 int main(void) {int i,j,n;int a[1001];int b[1001];int max;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&a[i]);b[i]=1;}for(i=0;i<n;i++){max=0;for(j=0;j<i;j++){if(a[i]>a[j]&&b[j]>max){max=b[j];}}b[i]=max+1;}max=0;for(i=0;i<n;i++){if(max<b[i])max=b[i];}printf("%d\n",max);return 0; }

其實(shí)還有更好的方法：

實(shí)現(xiàn)過(guò)程如下：

#define MAX_N 1010 #define INF 10010 int main() {int i;int n;cin>>n;int a[1010];for(i=0;i<n;i++){cin>>a[i];}int dp[MAX_N];fill(dp,dp+n,INF);for(i=0;i<n;i++){*lower_bound(dp,dp+n,a[i])=a[i];}cout<<lower_bound(dp,dp+n,INF)-dp<<endl; }

6.最大子段和

給定n個(gè)整數(shù)組成的序列a1,a2,…,an，求該序列子段和的最大值。最大子段和不能是負(fù)數(shù)，當(dāng)序列中均為負(fù)數(shù)時(shí)定義最大子段和為0。例如{-2, 11, -4, 13, -5, -2}的最大子段和為20。首先可以想到用分治的方法解決這個(gè)問(wèn)題，如果將給定的序列a[1..n]分成長(zhǎng)度相等的兩段a[1..n/2]和a[n/2+1:n]，分別求出這兩段的最大子段和。則該給定序列的最大子段和有三種情況：
和a[1…n/2]的最大子段和相同；
和a[n/2+1…n]的最大子段和相同；
最大子段和包含兩部分。
前兩種情形我們可以用遞歸方法求出，第三種情形可以分別求出兩部分的最大子段和值再相加。序列的最大子段和即為這三種情形的最大值。

實(shí)現(xiàn)過(guò)程如下：

int maxsub(int a[],int low,int high) {if(low==high) return a[low];int s1,s2,s3,s31,s32,i,j,sum;int mid=(low+high)/2;s1=maxsub(a,low,mid);s2=maxsub(a,mid+1,high);i=mid;s31=a[mid];while((s31+a[i-1]>s31)&&(i>low)){s31+=a[i-1];i--;}j=mid+1;s32=a[mid+1];while((s32+a[j+1]>s32)&&(j<high)){s32+=a[j+1];j++;}sum=s31+s32;if(sum<s1) sum=s1;if(sum<s2) sum=s2; return sum; }int main() {int a[6]={-2,11,-4,13,-5,-2};cout<<max(0,maxsub(a,0,5))<<endl; }

使用動(dòng)態(tài)規(guī)劃的解法能夠獲得更好的復(fù)雜度。若記b[j]=max(a[i]+a[i+1]+..+a[j]),其中1<=i<=j,并且1<=j<=n。注意一點(diǎn)，b[j]一定包括了a[j]。所求的最大子段和為max b[j]，1<=j<=n。由b[j]的定義可易知，當(dāng)b[j-1]>0時(shí)b[j]=b[j-1]+a[j]，否則b[j]=a[j]。故b[j]的動(dòng)態(tài)規(guī)劃遞歸式為:b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n。

int maxsub(int a[],int n) {int sum=0,b=0;for(int i=0;i<=n;i++) {if(b>0) b+=a[i];else b=a[i];if(b>sum) sum=b;}return sum; }int main() {int a[6]={-2,11,-4,13,-5,-2};cout<<maxsub(a,5)<<endl; }

7.最大子矩陣和

求一個(gè)最大為100*100矩陣中的子矩陣中元素之和的最大值

主要思想為將其轉(zhuǎn)化為一維數(shù)組求最大子段和，如果最優(yōu)解左起第i列，右止于第j列，那么我們相當(dāng)于把這些列的對(duì)應(yīng)位加和，成為一列，并對(duì)改列求最大子段和即可（降維思想）。

實(shí)現(xiàn)過(guò)程如下：

#define maxn 105 #define inf 0x3f3f3f3fint array[maxn][maxn]; int f[maxn][maxn][maxn];int main() {int n;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d", &array[i][j]);}}memset(f, 0, sizeof(f));int ans=-inf;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int sum=0;for(int k=j;k<=n;k++){sum+=array[i][k];f[i][j][k]=max(f[i-1][j][k]+sum,sum);//i是指行，j是起始列，k是終結(jié)列，f存的值為在ijk范圍內(nèi)的元素和最大值ans=max(ans,f[i][j][k]);}}}cout<<ans<<endl;return 0; }

8.凸多邊形最優(yōu)三角剖分

用多邊形頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即P={V0,V1,…,Vn}表示具有n+1條邊的凸多邊形。給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權(quán)之和為最小。若P={V0,V1……Vn}的最優(yōu)三角剖分T包含三角形V0VkVn,則T的權(quán)為三個(gè)部分權(quán)之和：三角形V0VkVn的權(quán)，多邊形{V0,V1……Vk}的權(quán)和多邊形{Vk,Vk+1……Vn}的權(quán)之和。可以斷言，由T確定的這兩個(gè)子多邊形的三角剖分也是最優(yōu)的。設(shè)t[i][j]為凸多邊形{Vi-1,Vi……Vj}的最優(yōu)三角剖分所對(duì)應(yīng)的最優(yōu)權(quán)值，則P的最優(yōu)權(quán)值為t[1][n]，有：

實(shí)現(xiàn)過(guò)程如下：

#define N 6 int weight[][N]= { {0,2,2,3,1,4}, {2,0,1,5,2,3}, {2,1,0,2,1,4}, {3,5,2,0,6,2}, {1,2,1,6,0,1}, {4,3,4,2,1,0} }; int t[N][N]; //t[i][j]表示多邊形{Vi-1VkVj}的最優(yōu)權(quán)值 int s[N][N]; //s[i][j]記錄Vi-1到Vj最優(yōu)三角剖分的中間點(diǎn)Kint get_weight(const int a, const int b, const int c) {return weight[a][b]+weight[b][c]+weight[c][a]; }void minweight() {int minval;for(int i=1;i<N;i++) t[i][i]=0;for(int r=2;r<N;r++){for(int i=1;i<N-r+1;i++){int j=i+r-1;minval=9999; for (int k=i;k<j;k++){t[i][j]=t[i][k]+t[k+1][j]+get_weight(i-1,k,j);if(t[i][j]<minval) {minval=t[i][j];s[i][j]=k; }}t[i][j]=minval; //取得多邊形Vi-1Vj的最小劃分權(quán)值 }} }void backtrack(int a, int b) {if (a==b) return;backtrack(a,s[a][b]);backtrack(s[a][b]+1,b); cout<<"最優(yōu)三角:"<<"v"<<a-1<<"v"<<s[a][b]<<"v"<<b<<endl; }int main() {minweight();cout<<"result:"<<t[1][N-1]<<endl;backtrack(1,5); }

9.最優(yōu)二叉搜索樹

在《算法導(dǎo)論》中對(duì)于這個(gè)問(wèn)題有詳細(xì)的描述。如果在二叉樹中查找元素不考慮概率及查找不成功的情況下，可以采用紅黑樹或者平衡二叉樹來(lái)搜索。而現(xiàn)實(shí)生活中，查找的關(guān)鍵字是有一定的概率的，就是說(shuō)有的關(guān)鍵字可能經(jīng)常被搜索，而有的很少被搜索，而且搜索的關(guān)鍵字可能不存在，為此需要根據(jù)關(guān)鍵字出現(xiàn)的概率構(gòu)建一個(gè)二叉樹。比如輸入法中針對(duì)用戶習(xí)慣可以自動(dòng)調(diào)整詞頻以減少用戶翻查次數(shù)，使得經(jīng)常用的詞匯被放置在前面，這樣就能有效地加快查找速度。給定一個(gè)由n個(gè)互異的關(guān)鍵字組成的有序序列K={k1<k2<k3<,……,<kn}和它們被查詢的概率P={p1,p2,p3,……,pn}，構(gòu)造一棵二叉查找樹使得查詢所有元素的總的代價(jià)最小。對(duì)于一個(gè)搜索樹，當(dāng)搜索的元素在樹內(nèi)時(shí)，表示搜索成功。當(dāng)不在樹內(nèi)時(shí)，表示搜索失敗，用一個(gè)虛葉子節(jié)點(diǎn)來(lái)標(biāo)示搜索失敗的情況，因此需要n+1個(gè)虛葉子節(jié)點(diǎn){d0<d1<……<dn}，對(duì)于應(yīng)di的概率序列是Q={q0,q1,……,qn}。其中d0表示搜索元素小于k1，dn表示搜索元素大于kn。di(0<i<n)表示搜索節(jié)點(diǎn)在ki和k(i+1)之間。因此有公式：

由每個(gè)關(guān)鍵字和每個(gè)虛擬鍵被搜索的概率，可以確定在一棵給定的二叉查找樹內(nèi)一次搜索的期望代價(jià)。設(shè)一次搜索的實(shí)際代價(jià)為檢查的節(jié)點(diǎn)個(gè)數(shù)，即所發(fā)現(xiàn)的節(jié)點(diǎn)的深度加上1。所以一次搜索的期望代價(jià)為：

需要注意的是一棵最優(yōu)二叉查找樹不一定是一棵整體高度最小的樹，也不一定總是把最大概率的關(guān)鍵字放在根部。對(duì)于這一點(diǎn)可以很容易找到反例。定義e[i,j]為搜索一棵包含關(guān)鍵字ki，……，kj的最優(yōu)二叉查找樹的期望代價(jià)，當(dāng)j=i-1時(shí)，說(shuō)明此時(shí)只有虛擬鍵di-1，故e[i,i-1] = qi-1；當(dāng)j≥i時(shí)，需要從ki，……，kj中選擇一個(gè)根kr，然后用關(guān)鍵字ki，……，kr-1來(lái)構(gòu)造一棵最優(yōu)二叉查找樹作為左子樹，用關(guān)鍵字kr+1，……，kj來(lái)構(gòu)造一棵最優(yōu)二叉查找樹作為右子樹。定義一棵有關(guān)鍵字ki，……，kj的子樹概率的總和為：

當(dāng)一棵樹成為一個(gè)節(jié)點(diǎn)的子樹時(shí)子樹中每個(gè)節(jié)點(diǎn)深度都增加1，期望搜索代價(jià)增加量為子樹中所有節(jié)點(diǎn)概率的總和。因此如果kr是一棵包含關(guān)鍵字ki，……，kj的最優(yōu)子樹的根，則有：

用root[i,j]來(lái)記錄關(guān)鍵字ki，……，kj的子樹的根，另外為了防止重復(fù)計(jì)算，用二維數(shù)組來(lái)保存w(i,j)的值，其中w[i,j] = w[i,j-1]+pj+qj。

實(shí)現(xiàn)過(guò)程如下：

#define N 5 #define MAX 999999.99999 void optimal_binary_search_tree(float *p,float *q,int n,float e[N+2][N+1],int root[N+1][N+1]); void Construct_Optimal_BST(int root[N+1][N+1],int i,int j,bool flag);int main() {float p[N+1]={0,0.15,0.10,0.05,0.10,0.20};float q[N+1]={0.05,0.10,0.05,0.05,0.05,0.10};float e[N+2][N+1];int root[N+1][N+1];int i,j;optimal_binary_search_tree(p,q,N,e,root);cout<<"最優(yōu)二叉查找樹的代價(jià)為: "<<e[1][N]<<endl;cout<<"最優(yōu)二叉查找樹的結(jié)構(gòu)描述如下："<<endl;Construct_Optimal_BST(root,1,N,0); }void optimal_binary_search_tree(float *p,float *q,int n,float e[N+2][N+1],int root[N+1][N+1]) {int i,j,k,r;float t;float w[N+2][N+1];for(i=1;i<=N+1;++i) {e[i][i-1]=q[i-1];w[i][i-1]=q[i-1];}for(k=1;k<=n;++k) //自底向上尋找最優(yōu)子樹 {for(i=1;i<=n-k+1;i++){j=i+k-1;e[i][j]=MAX;w[i][j]=w[i][j-1]+p[j]+q[j];for(r=i;r<=j;r++) {t=e[i][r-1]+e[r+1][j]+w[i][j];if(t<e[i][j]){e[i][j]=t;root[i][j]=r;}}}} }void Construct_Optimal_BST(int root[N+1][N+1],int i,int j,bool flag) { if(flag==0) { cout<<"k"<<root[i][j]<<" is root"<<endl; flag=1; } int r=root[i][j]; //如果左子樹是葉子 if(r-1<i) { cout<<"d"<<r-1<<" is the left child of "<<"K"<<r<<endl; } //如果左子樹不是葉子 else { cout<<"k"<<root[i][r-1]<<" is the left child of "<<"K"<<r<<endl; Construct_Optimal_BST(root,i,r-1,1); } //如果右子樹是葉子 if(r+1>j) { cout<<"d"<<j<<" is the right child of "<<"K"<<r<<endl; } //如果右子樹不是葉子 else { cout<<"k"<<root[r+1][j]<<" is the right child of "<<"K"<<r<<endl; Construct_Optimal_BST(root,r+1,j,1); } }

10.雙調(diào)歐幾里得旅行商問(wèn)題

這個(gè)問(wèn)題是《算法導(dǎo)論》中的思考題。給定平面上n個(gè)點(diǎn)，確定一條連接各點(diǎn)的最短閉合旅程。這個(gè)解的一般形式為NP的。J.L. Bentley建議通過(guò)只考慮雙調(diào)旅程來(lái)簡(jiǎn)化問(wèn)題。這種旅程即為從最左點(diǎn)開始，嚴(yán)格地從左到右直至最右點(diǎn)，然后嚴(yán)格地從右到左直至出發(fā)點(diǎn)。在這種情況下，存在確定的最優(yōu)雙調(diào)路線的O(n*n)時(shí)間的算法。

例如，a圖是最短閉合路線，但是它不是雙調(diào)的。b圖是最短的閉合雙調(diào)路線。
首先將各點(diǎn)按照x坐標(biāo)從小到大排列，定義從Pi到Pj的路徑為從Pi開始，從右到左一直到P1，然后從左到右一直到Pj。在這個(gè)路徑上，會(huì)經(jīng)過(guò)P1到Pmax(i,j)之間的所有點(diǎn)且每個(gè)點(diǎn)只經(jīng)過(guò)一次。定義d(i,j)為滿足這一條件的最短路徑，我們只考慮i>=j的情況。同時(shí)定義dist(i,j)為點(diǎn)Pi到Pj之間的直線距離。根據(jù)題意我們需要求的是d(n,n)。
關(guān)于子問(wèn)題d(i,j)的求解，分三種情況：
當(dāng)j<i-1時(shí)，由定義可知，點(diǎn)Pi-1一定在路徑Pi-Pj上，又由于j<i-1,因此Pi的左邊的相鄰點(diǎn)一定是Pi-1，故d(i,j)=d(i-1,j)+dist(i-1,i)。
當(dāng)j=i-1時(shí)，與Pi相鄰的那個(gè)點(diǎn)可能是P1到Pi-1中的任何一個(gè)，故d(i,i-1)=min{d(k,i-1)+dist(i,k)}，1<=k<i-1。
當(dāng)j=i時(shí)，同理，d(i,i)=min{d(k,i)+dist(i,k)}，1<=k<i。

實(shí)現(xiàn)過(guò)程如下：

#define INF 0x3f3f3f3f int n; double dis[550][550],dp[505][505]; struct Node { int x,y; }node[1500];bool cmp(Node a,Node b) { if(a.x!=b.x) return a.x<b.x; else return a.y<b.y; } void get_dis() { int x1,x2,y1,y2; for(int i=1;i<=n;++i){ x1=node[i].x;y1=node[i].y; for(int j=i;j<=n;++j){ x2=node[j].x;y2=node[j].y; dis[j][i]=dis[i][j]=sqrt((double)((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))); } } } int main() { int x,y; while(scanf("%d",&n)!=EOF){ memset(dis,0,sizeof(dis)); for(int i=1;i<=n;++i){ scanf("%d%d",&x,&y); node[i]=(Node){x,y}; } sort(node+1,node+n+1,cmp); get_dis(); dp[2][1]=dp[1][2]=dis[1][2]; dp[2][2]=2*dis[1][2]; for(int i=3;i<=n;++i){ for(int j=1;j<i-1;++j){ dp[j][i]=dp[i][j]=dp[i-1][j]+dis[i][i-1]; } dp[i][i-1]=dp[i-1][i]=dp[i][i]=INF; for(int k=1;k<i-1;++k){ if(dp[i][i-1]-(dp[k][i-1]+dis[k][i])>1e-3){ dp[i-1][i]=dp[i][i-1]=dp[k][i-1]+dis[k][i]; } } for(int k=1;k<i;++k){ if(dp[i][i]-(dp[k][i]+dis[k][i])>1e-3){ dp[i][i]=dp[k][i]+dis[k][i]; } } } printf("%.2f\n",dp[n][n]); } return 0; }

11.最大不相交子段和

求兩個(gè)不相交子段加起來(lái)的最大值。

將數(shù)組a[]從下標(biāo)k處劃分成兩部分a[1-k]和a[k+1,N]，用m1表示a[1-k]的最大字段和，m2表示a[k+1,N]的最大字段和，則 S = Max { m1, m2 } ( 其中k屬于區(qū)間[2-N-1] ，k不能取1和N，因?yàn)轭}目中j<p)

通過(guò)正向遍歷數(shù)組a求m1，逆向遍歷數(shù)組a求m2，最后根據(jù) S = Max { m1,m2 } 枚舉k即可。

const int INF = -0xfffffff; const int Max = 100000;// 對(duì)象 int n; int a[Max+1]; int b[Max+2]; int m1[Max+2], m2[Max+2]; // m1[i]:Max sum of sub array [0,i] of a// m2[i]:Max sum of sub array [i,n] of a int maxSum; // resint main() {while( scanf( "%d", &n ) && n ) {m1[0] = m2[n+1] = INF;memset( b, 0, sizeof(b) );for( int i = 1; i <= n; ++ i ) {scanf( "%d", &a[i] );if( b[i-1] >= 0 )b[i] = b[i-1] + a[i];else b[i] = a[i];m1[i] = b[i] > m1[i-1] ? b[i] : m1[i-1];}for( int i = n; i >= 1; -- i ) {if( b[i+1] >= 0 )b[i] = b[i+1] + a[i];elseb[i] = a[i];m2[i] = b[i] > m2[i+1] ? b[i] : m2[i+1];}maxSum = INF;for( int i = 1; i < n; ++ i ) {if( m1[i] + m2[i+1] > maxSum )maxSum = m1[i] + m2[i+1];}printf( "%d\n", maxSum );}return 0; }

12.最長(zhǎng)回文子串

回文是指正著讀和倒著讀，結(jié)果一些樣，比如abcba或abba。

舉個(gè)例子，我們要在一個(gè)字符串中要到最長(zhǎng)的回文子串。

暴力求解：

最容易想到的就是暴力破解，求出每一個(gè)子串，之后判斷是不是回文，找到最長(zhǎng)的那個(gè)。

求每一個(gè)子串時(shí)間復(fù)雜度O(N^2)，判斷子串是不是回文O(N)，兩者是相乘關(guān)系，所以時(shí)間復(fù)雜度為O(N^3)。

string findLongestPalindrome(string &s) {int length=s.size();//字符串長(zhǎng)度int maxlength=0;//最長(zhǎng)回文字符串長(zhǎng)度int start;//最長(zhǎng)回文字符串起始地址for(int i=0;i<length;i++)//起始地址for(int j=i+1;j<length;j++)//結(jié)束地址 {int tmp1,tmp2;for(tmp1=i,tmp2=j;tmp1<tmp2;tmp1++,tmp2--)//判斷是不是回文 {if(s.at(tmp1)!=s.at(tmp2))break;}if(tmp1>=tmp2&&j-i>maxlength){maxlength=j-i+1;start=i;}}if(maxlength>0)return s.substr(start,maxlength);//求子串return NULL; }

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

回文字符串的子串也是回文，比如P[i,j]（表示以i開始以j結(jié)束的子串）是回文字符串，那么P[i+1,j-1]也是回文字符串。這樣最長(zhǎng)回文子串就能分解成一系列子問(wèn)題了。這樣需要額外的空間O(N^2)，算法復(fù)雜度也是O(N^2)。

首先定義狀態(tài)方程和轉(zhuǎn)移方程：

P[i,j]=0表示子串[i,j]不是回文串。P[i,j]=1表示子串[i,j]是回文串。

string findLongestPalindrome(string &s) {const int length=s.size();int maxlength=0;int start;bool P[50][50]={false};for(int i=0;i<length;i++)//初始化準(zhǔn)備 {P[i][i]=true;if(i<length-1&&s.at(i)==s.at(i+1)){P[i][i+1]=true;start=i;maxlength=2;}}for(int len=3;len<=length;len++)//子串長(zhǎng)度for(int i=0;i<=length-len;i++)//子串起始地址 {int j=i+len-1;//子串結(jié)束地址if(P[i+1][j-1]&&s.at(i)==s.at(j)){P[i][j]=true;maxlength=len;start=i;}}if(maxlength>=2)return s.substr(start,maxlength);return NULL; }

中心擴(kuò)展

中心擴(kuò)展就是把給定的字符串的每一個(gè)字母當(dāng)做中心，向兩邊擴(kuò)展，這樣來(lái)找最長(zhǎng)的子回文串。算法復(fù)雜度為O(N^2)。

但是要考慮兩種情況： 1、像aba，這樣長(zhǎng)度為奇數(shù)。 2、想abba，這樣長(zhǎng)度為偶數(shù)。 實(shí)現(xiàn)過(guò)程如下： string findLongestPalindrome(string &s) {const int length=s.size();int maxlength=0;int start;for(int i=0;i<length;i++)//長(zhǎng)度為奇數(shù) {int j=i-1,k=i+1;while(j>=0&&k<length&&s.at(j)==s.at(k)){if(k-j+1>maxlength){maxlength=k-j+1;start=j;}j--;k++;}}for(int i=0;i<length;i++)//長(zhǎng)度為偶數(shù) {int j=i,k=i+1;while(j>=0&&k<length&&s.at(j)==s.at(k)){if(k-j+1>maxlength){maxlength=k-j+1;start=j;}j--;k++;}}if(maxlength>0)return s.substr(start,maxlength);return NULL; }

Manacher法

Manacher法只能解決例如aba這樣長(zhǎng)度為奇數(shù)的回文串，對(duì)于abba這樣的不能解決，于是就在里面添加特殊字符。我是添加了“#”，使abba變?yōu)閍#b#b#a。這個(gè)算法就是利用已有回文串的對(duì)稱性來(lái)計(jì)算的，具體算法復(fù)雜度為O(N)，我沒看出來(lái)，因?yàn)橛袃蓚€(gè)嵌套的for循環(huán)。

具體原理利用已知回文串的左半部分來(lái)推導(dǎo)右半部分

首先,在字符串s中,用rad[i]表示第i個(gè)字符的回文半徑,即rad[i]盡可能大,且滿足:
s[i-rad[i],i-1]=s[i+1,i+rad[i]]
很明顯,求出了所有的rad,就求出了所有的長(zhǎng)度為奇數(shù)的回文子串.
至于偶數(shù)的怎么求,最后再講.
假設(shè)現(xiàn)在求出了rad[1..i-1],現(xiàn)在要求后面的rad值,并且通過(guò)前面的操作,得知了當(dāng)前字符i的rad值至少為j.現(xiàn)在通過(guò)試圖擴(kuò)大j來(lái)掃描,求出了rad[i].再假設(shè)現(xiàn)在有個(gè)指針k,從1循環(huán)到rad[i],試圖通過(guò)某些手段來(lái)求出[i+1,i+rad[i]]的rad值.
根據(jù)定義,黑色的部分是一個(gè)回文子串,兩段紅色的區(qū)間全等.
因?yàn)橹耙呀?jīng)求出了rad[i-k],所以直接用它.有3種情況:

①rad[i]-k<rad[i-k]
如圖,rad[i-k]的范圍為青色.因?yàn)楹谏牟糠质腔匚牡?且青色的部分超過(guò)了黑色的部分,所以rad[i+k]肯定至少為rad[i]-k,即橙色的部分.那橙色以外的部分就不是了嗎?這是肯定的.因?yàn)槿绻壬酝獾牟糠忠彩腔匚牡?那么根據(jù)青色和紅色部分的關(guān)系,可以證明黑色部分再往外延伸一點(diǎn)也是一個(gè)回文子串,這肯定不可能,因此rad[i+k]=rad[i]-k.為了方便下文,這里的rad[i+k]=rad[i]-k=min(rad[i]-k,rad[i-k]).

?

②rad[i]-k>rad[i-k]
如圖,rad[i-k]的范圍為青色.因?yàn)楹谏牟糠质腔匚牡?且青色的部分在黑色的部分里面,根據(jù)定義,很容易得出:rad[i+k]=rad[i-k].為了方便下文,這里的rad[i+k]=rad[i-k]=min(rad[i]-k,rad[i-k]).

根據(jù)上面兩種情況,可以得出結(jié)論:當(dāng)rad[i]-k!=rad[i-k]的時(shí)候,rad[i+k]=min(rad[i]-k,rad[i-k]).
注意:當(dāng)rad[i]-k==rad[i-k]的時(shí)候,就不同了,這是第三種情況:

如圖,通過(guò)和第一種情況對(duì)比之后會(huì)發(fā)現(xiàn),因?yàn)榍嗌牟糠譀]有超出黑色的部分,所以即使橙色的部分全等,也無(wú)法像第一種情況一樣引出矛盾,因此橙色的部分是有可能全等的,但是,根據(jù)已知的信息,我們不知道橙色的部分是多長(zhǎng),因此就把i指針移到i+k的位置,j=rad[i-k](因?yàn)樗膔ad值至少為rad[i-k]),等下次循環(huán)的時(shí)候再做了.
整個(gè)算法就這樣.
至于時(shí)間復(fù)雜度為什么是O(n),我已經(jīng)證明了,但很難說(shuō)清楚.所以自己體會(huì)吧.
上文還留有一個(gè)問(wèn)題,就是這樣只能算出奇數(shù)長(zhǎng)度的回文子串,偶數(shù)的就不行.怎么辦呢?有一種直接但比較笨的方法,就是做兩遍(因?yàn)閮蓚€(gè)程序是差不多的,只是rad值的意義和一些下標(biāo)變了而已).但是寫兩個(gè)差不多的程序是很痛苦的,而且容易錯(cuò).所以一種比較好的方法就是在原來(lái)的串中每?jī)蓚€(gè)字符之間加入一個(gè)特殊字符,再做.如:aabbaca,把它變成(#a#a#b#b#a#c#a#)，左右的括號(hào)是為了使得算法不至于越界。這樣的話,無(wú)論原來(lái)的回文子串長(zhǎng)度是偶數(shù)還是奇數(shù),現(xiàn)在都變成奇數(shù)了.

測(cè)試代碼中我沒過(guò)濾掉“#”。 #define min(x, y) ((x)<(y)?(x):(y)) #define max(x, y) ((x)<(y)?(y):(x)) string findLongestPalindrome3(string s) {int length=s.size();for(int i=0,k=1;i<length-1;i++)//給字符串添加 # {s.insert(k,"#");k=k+2;}length=length*2-1;//添加#后字符串長(zhǎng)度int *rad=new int[length]();rad[0]=0;for(int i=1,j=1,k;i<length;i=i+k){while(i-j>=0&&i+j<length&&s.at(i-j)==s.at(i+j))j++;rad[i]=j-1;for(k=1;k<=rad[i]&&rad[i-k]!=rad[i]-k;k++)//鏡像,遇到rad[i-k]=rad[i]-k停止，這時(shí)不用從j=1開始比較rad[i+k]=min(rad[i-k],rad[i]-k);j=max(j-k,0);//更新j }int max=0;int center;for(int i=0;i<length;i++){if(rad[i]>max){max=rad[i];center=i;}}return s.substr(center-max,2*max+1);}

13.KMP算法

KMP算法用于字符串匹配，kmp算法完成的任務(wù)是：給定兩個(gè)字符串O和f，長(zhǎng)度分別為n和m，判斷f是否在O中出現(xiàn)，如果出現(xiàn)則返回出現(xiàn)的位置。常規(guī)方法是遍歷a的每一個(gè)位置，然后從該位置開始和b進(jìn)行匹配，但是這種方法的復(fù)雜度是O(nm)。kmp算法通過(guò)一個(gè)O(m)的預(yù)處理，使匹配的復(fù)雜度降為O(n+m)。

在這里我只能簡(jiǎn)單的進(jìn)行個(gè)小結(jié)，有興趣的同學(xué)可以參考我之前寫過(guò)的一篇文章KMP算法學(xué)習(xí)(詳解)

樸素匹配算法需要兩個(gè)指針i，j都遍歷一遍字符串，故復(fù)雜度m*n

KMP算法i指針不回溯，j指針的回溯參考next數(shù)組，體現(xiàn)了動(dòng)態(tài)規(guī)劃的思想

原理如下：

藍(lán)色表示匹配，紅色為失配

分析藍(lán)色部分

如果存在最長(zhǎng)公共前后綴的話，比如這樣：

就可以在下次匹配的時(shí)候用，這樣避免了i的回溯

next數(shù)組的意義：當(dāng)模式匹配串T失效的時(shí)候，next數(shù)組對(duì)應(yīng)的元素知道應(yīng)該使用T串的哪個(gè)元素進(jìn)行下一輪匹配

實(shí)現(xiàn)過(guò)程如下：

void get_next(string T, int *next) {int i = 1; //后綴int j = 0; //前綴next[1] = 0;while (i < T[0]) //T[0]表示字符串長(zhǎng)度 {if (j == 0 || T[i] == T[j]){i++;j++;next[i] = j;}elsej = next[j];} }int KMP(string S, string T, int pos) {int i = pos; //標(biāo)記主串S下標(biāo)int j = 1; //匹配串下標(biāo)int next[255];get_next(T, next);while (i <= S[0] && j <= T[0]) //0位置都放字符串長(zhǎng)度 {if (j == 0 || S[i] == T[j]){i++;j++;}elsej = next[j]; //j退回到合適位置，i不用再回溯了if (j > T[0]) //如果存在j在匹配完最后一個(gè)元素后又++了，所以會(huì)大于長(zhǎng)度return i - T[0]; //i的位置減去匹配串的長(zhǎng)度就是匹配串出現(xiàn)的位置elsereturn 0;} }

會(huì)出現(xiàn)一種特殊情況：

S = “aaaabcde”

T = "aaaaax"

這樣的話next數(shù)組為012345，實(shí)際上由于前面都是a，直接調(diào)到第一個(gè)a就可以了，期望的next數(shù)組為000005

這樣next數(shù)組構(gòu)造改為12-15行

改進(jìn)方案：

void get_next(string T, int *next) {int i = 1; //后綴int j = 0; //前綴next[1] = 0;while (i < T[0]) //T[0]表示字符串長(zhǎng)度 {if (j == 0 || T[i] == T[j]){i++;j++;if (T[i] != T[j])next[i] = j;elsenext[i] = next[j];}elsej = next[j];} }

14.硬幣找零問(wèn)題

假設(shè)有幾種硬幣，如1 5 10 20 50 100，并且數(shù)量無(wú)限。請(qǐng)找出能夠組成某個(gè)數(shù)目的找零所使用最少的硬幣數(shù)。

解法：

用待找零的數(shù)值k描述子結(jié)構(gòu)/狀態(tài)，記作sum[k]，其值為所需的最小硬幣數(shù)。對(duì)于不同的硬幣面值coin[0...n]，有sum[k] = min(sum[k-coin[0]] , sum[k-coin[1]], ...)+1。對(duì)應(yīng)于給定數(shù)目的找零total，需要求解sum[total]的值。

注意要從前往后算，從后往前算無(wú)法保存狀態(tài)，需要遞歸，效率很低，就不是動(dòng)態(tài)規(guī)劃了

#define MaxNum pow(2,31) - 1 int main() {int n;while (cin >> n){vector<int> c(n + 1, 0);for (int i = 1; i <= n; i++){if (i == 1 || i == 5 || i == 10 || i == 20 || i == 50 || i == 100){c[i] = 1;continue;}int curMin = MaxNum;if (i - 1 > 0)curMin = c[i - 1] < curMin ? c[i - 1] : curMin;if (i - 5 > 0)curMin = c[i - 5] < curMin ? c[i - 5] : curMin;if (i - 10 > 0)curMin = c[i - 10] < curMin ? c[i - 10] : curMin;if (i - 20 > 0)curMin = c[i - 20] < curMin ? c[i - 20] : curMin;if (i - 50 > 0)curMin = c[i - 50] < curMin ? c[i - 50] : curMin;if (i - 100 > 0)curMin = c[i - 100] < curMin ? c[i - 100] : curMin;c[i] = curMin + 1;}cout << c[n] << endl;}system("pause");return 0; }

15.找平方個(gè)數(shù)最小

給一個(gè)正整數(shù)?n,?找到若干個(gè)完全平方數(shù)(比如1,?4,?9,?...?)使得他們的和等于?n。你需要讓平方數(shù)的個(gè)數(shù)最少。
給出?n?=?12,?返回?3?因?yàn)?12?=?4?+?4?+?4。
給出?n?=?13,?返回?2?因?yàn)?13?=?4?+?9。

實(shí)現(xiàn)過(guò)程如下：

int findMin(int n) {int *result = new int(n + 1);result[0] = 0;for (int i = 1; i <= n; i++){int minNum = i;for (int j = 1;; j++){if (i >= j * j){int tmp = result[i - j*j] + 1;minNum = tmp < minNum ? tmp : minNum;}elsebreak;}result[i] = minNum;}return result[n]; }int main() {int n;while (cin >> n)cout << findMin(n) << endl; }

16.N*N方格內(nèi)的走法問(wèn)題

有一個(gè)n*n的方格，從左上角走到右下角有多少種最短路徑的走法？

若不加最短路徑則n^(n-1)種走法。加上了最短路徑就是說(shuō)橫向的距離為n-1，縱向的距離為n-1.總共的距離是2(n-1)步走到。

實(shí)現(xiàn)過(guò)程如下：

int main() {int n;while (cin >> n){vector<vector<int>> dp(n+1, vector<int>(n+1, 1));for (int i = 1; i <= n;i++){for (int j = 1; j <= n;j++){dp[i][j] = dp[i][j - 1] + dp[i - 1][j];}}cout << dp[n][n] << endl;} }

17.樓層拋珠問(wèn)題

某幢大樓有100層。你手里有兩顆一模一樣的玻璃珠。當(dāng)你拿著玻璃珠在某一層往下扔的時(shí)候，一定會(huì)有兩個(gè)結(jié)果，玻璃珠碎了或者沒碎。這幢大樓有個(gè)臨界樓層。低于它的樓層，往下扔玻璃珠，玻璃珠不會(huì)碎，等于或高于它的樓層，扔下玻璃珠，玻璃珠一定會(huì)碎。玻璃珠碎了就不能再扔。現(xiàn)在讓你設(shè)計(jì)一種方式，使得在該方式下，最壞的情況扔的次數(shù)比其他任何方式最壞的次數(shù)都少。也就是設(shè)計(jì)一種最有效的方式。

例如：有這樣一種方式，第一次選擇在60層扔，若碎了，說(shuō)明臨界點(diǎn)在60層及以下樓層，這時(shí)只有一顆珠子，剩下的只能是從第一層，一層一層往上實(shí)驗(yàn)，最壞的情況，要實(shí)驗(yàn)59次，加上之前的第一次，一共60次。若沒碎，則只要從61層往上試即可，最多只要試40次，加上之前一共需41次。兩種情況取最多的那種。故這種方式最壞的情況要試60次。仔細(xì)分析一下。如果不碎，我還有兩顆珠子，第二顆珠子會(huì)從N+1層開始試嗎？很顯然不會(huì)，此時(shí)大樓還剩100-N層，問(wèn)題就轉(zhuǎn)化為100-N的問(wèn)題了。

那該如何設(shè)計(jì)方式呢？

根據(jù)題意很容易寫出狀態(tài)轉(zhuǎn)移方程：N層樓如果從n層投下玻璃珠，最壞的嘗試次數(shù)是：

那么所有層投下的最壞嘗試次數(shù)的最小值即為問(wèn)題的解：。其中F(1)=1.

實(shí)現(xiàn)過(guò)程如下：

int max(int a, int b) {return (a > b)? a : b; }int dp[101]; //N<=100; int floorThr(int N) {for (int i = 2; i <= N; i++){dp[i] = i;for (int j = 1; j<i; j++){int tmp = max(j, 1 + dp[i - j]); //j的遍歷相當(dāng)于把每層都試一遍if (tmp<dp[i])dp[i] = tmp;}}return dp[N]; }int main() {dp[0] = 0;dp[1] = 1;int dis = floorThr(100);cout << dis << endl;system("Pause"); }

18.字符串相似度/編輯距離(edit distance)

許多程序會(huì)大量使用字符串。對(duì)于不同的字符串，我們希望能夠有辦法判斷其相似程度。我們定義了一套操作方法來(lái)把兩個(gè)不相同的字符串變得相同，具體的操作方法為：
1.修改一個(gè)字符（如把“a”替換為“b”）。
2.增加一個(gè)字符（如把“abdd”變?yōu)椤癮ebdd”）。
3.刪除一個(gè)字符（如把“travelling”變?yōu)椤皌raveling”）。
比如，對(duì)于“abcdefg”和“abcdef”兩個(gè)字符串來(lái)說(shuō)，我們認(rèn)為可以通過(guò)增加/減少一個(gè)“g“的方式來(lái)達(dá)到目的。上面的兩種方案，都僅需要一次操作。把這個(gè)操作所需要的次數(shù)定義為兩個(gè)字符串的距離，給定任意兩個(gè)字符串，你是否能寫出一個(gè)算法來(lái)計(jì)算出它們的距離？

不難看出，兩個(gè)字符串的距離肯定不超過(guò)它們的長(zhǎng)度之和（我們可以通過(guò)刪除操作把兩個(gè)串都轉(zhuǎn)化為空串）。雖然這個(gè)結(jié)論對(duì)結(jié)果沒有幫助，但至少可以知道，任意兩個(gè)字符串的距離都是有限的。
我們還是應(yīng)該集中考慮如何才能把這個(gè)問(wèn)題轉(zhuǎn)化成規(guī)模較小的同樣的問(wèn)題。如果有兩個(gè)串A=xabcdae和B=xfdfa，它們的第一個(gè)字符是相同的，只要計(jì)算A[2,…,7]=abcdae和B[2,…,5]=fdfa的距離就可以了。但是如果兩個(gè)串的第一個(gè)字符不相同，那么可以進(jìn)行如下的操作（lenA和lenB分別是A串和B串的長(zhǎng)度）：
1．刪除A串的第一個(gè)字符，然后計(jì)算A[2,…,lenA]和B[1,…,lenB]的距離。
2．刪除B串的第一個(gè)字符，然后計(jì)算A[1,…,lenA]和B[2,…,lenB]的距離。
3．修改A串的第一個(gè)字符為B串的第一個(gè)字符，然后計(jì)算A[2,…,lenA]和B[2,…,lenB]的距離。
4．修改B串的第一個(gè)字符為A串的第一個(gè)字符，然后計(jì)算A[2,…,lenA]和B[2,…,lenB]的距離。
5．增加B串的第一個(gè)字符到A串的第一個(gè)字符之前，然后計(jì)算A[1,…,lenA]和B[2,…,lenB]的距離。
6．增加A串的第一個(gè)字符到B串的第一個(gè)字符之前，然后計(jì)算A[2,…,lenA]和B[1,…,lenB]的距離。

在這個(gè)題目中，我們并不在乎兩個(gè)字符串變得相等之后的字符串是怎樣的。所以，可以將上面6個(gè)操作合并為：
1.一步操作之后，再將A[2,…,lenA]和B[1,…,lenB]變成相同字符串。
2.一步操作之后，再將A[1,…,lenA]和B[2,…,lenB]變成相同字符串。
3.一步操作之后，再將A[2,…,lenA]和B[2,…,lenB]變成相同字符串。

這樣，很快就可以完成一個(gè)遞歸程序。

代碼實(shí)現(xiàn)如下：

int calStringDis(string strA, int pABegin,int pAEnd,string strB, int pBBegin,int pBEnd) { if (pABegin > pAEnd) { if (pBBegin > pBEnd) return 0; else return pBEnd - pBBegin + 1; } if (pBBegin > pBEnd) { if(pABegin > pAEnd) return 0; else return pAEnd - pABegin + 1; } if (strA[pABegin] == strB[pBBegin]) { return calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin+1,pBEnd); } else { int t1 = calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin+2,pBEnd); int t2 = calStringDis(strA,pABegin+2,pAEnd,strB,pBBegin+1,pBEnd); int t3 = calStringDis(strA,pABegin+2,pAEnd,strB,pBBegin+2,pBEnd); return minValue(t1,t2,t3)+1; } }

在遞歸的過(guò)程中，有些數(shù)據(jù)被重復(fù)計(jì)算了。

很經(jīng)典的可使用動(dòng)態(tài)規(guī)劃方法解決的題目，和計(jì)算兩字符串的最長(zhǎng)公共子序列相似。

設(shè)Ai為字符串A(a1a2a3 … am)的前i個(gè)字符（即為a1,a2,a3 … ai）
設(shè)Bj為字符串B(b1b2b3 … bn)的前j個(gè)字符（即為b1,b2,b3 … bj）

設(shè) L(i,j)為使兩個(gè)字符串和Ai和Bj相等的最小操作次數(shù)。
當(dāng)ai==bj時(shí) 顯然 L(i,j) = L(i-1,j-1)
當(dāng)ai!=bj時(shí)?

　　若將它們修改為相等，則對(duì)兩個(gè)字符串至少還要操作L(i-1,j-1)次
?　 若刪除ai或在bj后添加ai，則對(duì)兩個(gè)字符串至少還要操作L(i-1,j)次
?　 若刪除bj或在ai后添加bj，則對(duì)兩個(gè)字符串至少還要操作L(i,j-1)次
?　 此時(shí)L(i,j) = min( L(i-1,j-1), L(i-1,j), L(i,j-1) ) + 1?

顯然，L(i,0)=i，L(0,j)=j, 再利用上述的遞推公式，可以直接計(jì)算出L(i,j)值。

代碼實(shí)現(xiàn)如下：

int minValue(int a, int b, int c) {int t = a <= b ? a:b;return t <= c ? t:c; }int calculateStringDistance(string strA, string strB) {int lenA = (int)strA.length()+1;int lenB = (int)strB.length()+1;int **c = new int*[lenA];for(int i = 0; i < lenA; i++)c[i] = new int[lenB];for(int i = 0; i < lenA; i++) c[i][0] = i;for(int j = 0; j < lenB; j++) c[0][j] = j;c[0][0] = 0;for(int i = 1; i < lenA; i++){for(int j = 1; j < lenB; j++){if(strB[j-1] == strA[i-1])c[i][j] = c[i-1][j-1];elsec[i][j] = minValue(c[i][j-1], c[i-1][j], c[i-1][j-1]) + 1;}}int ret = c[lenA-1][lenB-1];for(int i = 0; i < lenA; i++)delete [] c[i];delete []c;return ret; }

19.N皇后問(wèn)題

N皇后問(wèn)題是一個(gè)以國(guó)際象棋為背景的問(wèn)題：如何能夠在 NxN 的國(guó)際象棋棋盤上放置八個(gè)皇后，使得任何一個(gè)皇后都無(wú)法直接吃掉其他的皇后？為了達(dá)到此目的，任兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上。

我們可以通過(guò)下面的圖標(biāo)來(lái)展示回溯法的過(guò)程
從而更加有助于我們的理解

我們以4x4為例：

我們?cè)谠囂降倪^(guò)程中，皇后的放置需要檢查他的位置是否和已經(jīng)放置好的皇后發(fā)生沖突，為此需要以及檢查函數(shù)來(lái)檢查當(dāng)前要放置皇后的位置，是不是和其他已經(jīng)放置的皇后發(fā)生沖突

假設(shè)有兩個(gè)皇后被放置在（i，j）和（k，l）的位置上，明顯，當(dāng)且僅當(dāng)|i-k|=|j-l| 時(shí)，兩個(gè)皇后才在同一條對(duì)角線上。

（1）先從首位開始檢查，如果不能放置，接著檢查該行第二個(gè)位置，依次檢查下去，直到在該行找到一個(gè)可以放置一個(gè)皇后的地方，然后保存當(dāng)前狀態(tài)，轉(zhuǎn)到下一行重復(fù)上述方法的檢索。
（2）如果檢查了該行所有的位置均不能放置一個(gè)皇后，說(shuō)明上一行皇后放置的位置無(wú)法讓所有的皇后找到自己合適的位置，因此就要回溯到上一行，重新檢查該皇后位置后面的位置。

int PLACE(int n) /* 檢查當(dāng)前列能否放置皇后 */ {//queen[i] == queen[n]用于保證元素不能再同一列//abs(queen[i] - queen[n]) == abs(n - i)用于約束元素不能再同一行且不能再同一條斜線上int i;for(i = 0; i < n; i++) /* 檢查橫排和對(duì)角線上是否可以放置皇后 */{if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == abs(n - i)){return 0;}}return 1; }

具體的實(shí)現(xiàn)代碼如下：

#define max 4 //sum用于描述解的可能的個(gè)數(shù)，每當(dāng)輸出一次復(fù)合要求的位置 //sum的數(shù)量就會(huì)被+1 int queen[max], sum=0; /* max為棋盤最大坐標(biāo) */void show() /* 輸出所有皇后的坐標(biāo) */ {int i;printf("(");//i代表行數(shù)，queen[i]代表當(dāng)前行元素所處的列數(shù)，//注意此處下標(biāo)是從0開始的for(i = 0; i < max; i++){printf(" %d", queen[i]+1);}printf(")\n");//每次輸出一種解的時(shí)候，那么他的解的數(shù)量就會(huì)增加1sum++; }//此函數(shù)用于判斷皇后當(dāng)前皇后是否可以放在此位置 int PLACE(int n) /* 檢查當(dāng)前列能否放置皇后 */ {//queen[i] == queen[n]用于保證元素不能再同一列//abs(queen[i] - queen[n]) == abs(n - i)用于約束元素不能再同一行且不能再同一條斜線上int i;for(i = 0; i < n; i++) /* 檢查橫排和對(duì)角線上是否可以放置皇后 */{if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == abs(n - i)){return 0;}}return 1; }//核心函數(shù)，回溯法的思想 void NQUEENS(int n) /* 回溯嘗試皇后位置,n為橫坐標(biāo) */ {int i;for(i = 0; i < max; i++){//首先將皇后放在第0列的位置，對(duì)于第一次來(lái)說(shuō)是肯定成立的//所以第一次將皇后放在第0行0列的位置queen[n] = i; /* 將皇后擺到當(dāng)前循環(huán)到的位置 */if(PLACE(n)){if(n == max - 1){show(); /* 如果全部擺好，則輸出所有皇后的坐標(biāo) */}else{NQUEENS(n + 1); /* 否則繼續(xù)擺放下一個(gè)皇后 */}}} }int main() {NQUEENS(0); /* 從橫坐標(biāo)為0開始依次嘗試 */printf("\n");printf("總共的解法有%d種\n", sum);return 0; }

習(xí)題練習(xí)推薦

• N皇后問(wèn)題是一個(gè)經(jīng)典的問(wèn)題，在一個(gè)N*N的棋盤上放置N個(gè)皇后，每行一個(gè)并使其不能互相攻擊（同一行、同一列、同一斜線上的皇后都會(huì)自動(dòng)攻擊），求出有多少種合法的放置方法。輸出N皇后問(wèn)題所有不同的擺放情況個(gè)數(shù)。---九度OJ1254
• 將一堆正整數(shù)分為2組，要求2組的和相差最小.---51Nod 1007 參考題解在這里，關(guān)于01背包問(wèn)題更多題目推薦參考這里
• 符號(hào)三角形的 第1行有n個(gè)由“+”和”-“組成的符號(hào) ，以后每行符號(hào)比上行少1個(gè)，2個(gè)同號(hào)下面是”+“，2個(gè)異 號(hào)下面是”-“ 。計(jì)算有多少個(gè)不同的符號(hào)三角形，使其所含”+“ 和”-“ 的個(gè)數(shù)相同 。---hdu2510
• 給出兩個(gè)字符串，求出這樣的一個(gè)最長(zhǎng)的公共子序列的長(zhǎng)度：子序列中的每個(gè)字符都能在兩個(gè)原串中找到， 而且每個(gè)字符的先后順序和原串中的先后順序一致。---POJ1458
• 求出最長(zhǎng)上升子序列的長(zhǎng)度。---百練2757
• 從三角形頂部數(shù)字走，每次只能走到這個(gè)數(shù)字的左下角或者右下角的數(shù)字，直到底部，計(jì)算走過(guò)的線路的數(shù)字之和，求這個(gè)和的最大值。---POJ1163。
• 給出兩個(gè)串，分別為a，b，問(wèn)a串在b串中出現(xiàn)了幾次？(其實(shí)位置不同，就算不同的串)。---hdu1686

更多題目推薦未來(lái)待續(xù)更新

參考文獻(xiàn)

• 動(dòng)態(tài)規(guī)劃百度百科：https://baike.baidu.com/item/動(dòng)態(tài)規(guī)劃/529408?fr=aladdin
• 回溯算法入門及經(jīng)典案例剖析(初學(xué)者必備寶典)：http://www.cnblogs.com/ECJTUACM-873284962/p/8447050.html#_nav_14
• 動(dòng)態(tài)規(guī)劃：http://www.doc88.com/p-6408257243193.html
• 麻省理工學(xué)院公開課：算法導(dǎo)論 ---動(dòng)態(tài)規(guī)劃，最長(zhǎng)公共子序列：http://open.163.com/movie/2010/12/L/4/M6UTT5U0I_M6V2U1HL4.html

轉(zhuǎn)載于:https://www.cnblogs.com/ECJTUACM-873284962/p/8644075.html

總結(jié)

以上是生活随笔為你收集整理的浅谈我对动态规划的一点理解---大家准备好小板凳，我要开始吹牛皮了~~~的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。