1. Fibonacci數列
F(0) = 1, F(1) = 1
F(n+1) = F(n)+F(n-1)
最友善的方法當然是遞歸,但遞歸對堆棧需求很大。最小記憶體使用隻需要兩個變量
int F(int n)
{
int a=1, b=1, t;
if( n ==0 || n ==1) return 1;
for( int i=2; i<=n; i++)
{
t = a+b;
a = b;
b = t;
}
return t;
}
很簡單，但是利用輔助空間的思想是典型的動态規劃。
2. Maximun value contiguous subsequence
有一實數數列A[i], 求區間l..m使得Sum(A[l]..A[m])最大
假設對于某個元素下标j-1, 目前最大sum是M[j-1]
那麼對于j, 目前最大sum就是max(M[j-1]+A[j], A[j])
double m[N], max_sum;
m[0]=a[0];
max_sum=m[0];
for(int i=1; i<N; i++)
{
m[i]=max(m[i-1]+a[i], a[i]);
max_sum = max(max_sum, m[i]);
}
讓我們把問題擴充到兩維,有個a(1..n,1..m),求其一子矩陣a(i..j,k..l)其元素的和最大.
上面的問題中用到了輔助數組m[i], 這次需要用到三維輔助數組了.
定義m(i,j,k):=以a(k,i..j)為最後一行的子矩陣的最大和, m(i,j,0)=sum{a(0,i..j)}
那麼 m(i,j,k)=max{0,m(i,j,k-1)} + sum{a(k,i..j)}
複雜度是O(n^3)
3. coins
Given a list of N coins, their values (V1 , V2 , ... , VN ), and the total sum S . Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S .
i. Sort the coins value ascending… Suppose there is no value “1” inside the values. Reconstruct the array, make an array V[0..N], let V[0]=1, and V[i]<V[i+1] for any i
ii. Make an auxiliary array C, C[i][j] is the min number of coins to make change for the amount of j, by coins from 0 through i. j=0..S, i=1..N 可以容易發現,因為V[0]=1, 是以每一個C[0][j]都等于j/1=j
iii. for i=1 to N
for j=0 to S
if( V[i]>j || C[i-1][j]<1+C[i][j-V[i]])
C[i][j]=C[i-1][j];
else
C[i][j]=1+C[i][j-V[i]];
如果需要記錄用到了那些硬币，再開一個數組used[i][j]，表示硬币值V[i]是否在j的最小集中出現，加在else裡面。
http://condor.depaul.edu/~rjohnson/algorithm/coins.pdf
4. Maximum size square sub-matrix with all 1s
Given a binary matrix, find out the maximum size square sub-matrix with all 1s.
For example, consider the below binary matrix.
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0 The maximum square sub-matrix with all set bits is
1 1 1
1 1 1
1 1 1 Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.
1) Construct a sum matrix S[R][C] for the given M[R][C]. a) Copy first row and first columns as it is from M[][] to S[][] b) For other entries, use following expressions to construct S[][] If M[i][j] is 1 then S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1 Else /*If M[i][j] is 0*/ S[i][j] = 0 2) Find the maximum entry in S[m][n] 3) Using the value and coordinates of maximum entry in S[i], print sub-matrix of M[][] For the given M[R][C] in above example, constructed S[R][C] would be:
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 2 2 0
1 2 2 3 1
0 0 0 0 0 The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.
代碼如下
#include<stdio.h>
#define bool int
#define R 6
#define C 5
void printMaxSubSquare(bool M[R][C])
{
int i,j;
int S[R][C];
int max_of_s, max_i, max_j;
for(i = 0; i < R; i++)
S[i][0] = M[i][0];
for(j = 0; j < C; j++)
S[0][j] = M[0][i];
for(i = 1; i < R; i++)
{
for(j = 1; j < C; j++)
{
if(M[i][j] == 1)
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;
else
S[i][j] = 0;
}
}
max_of_s = S[0][0]; max_i = 0; max_j = 0;
for(i = 0; i < R; i++)
{
for(j = 0; j < C; j++)
{
if(max_of_s < S[i][j])
{
max_of_s = S[i][j];
max_i = i;
max_j = j;
}
}
}
printf("/n Maximum size sub-matrix is: /n");
for(i = max_i; i > max_i - max_of_s; i--)
{
for(j = max_j; j > max_j - max_of_s; j--)
{
printf("%d ", M[i][j]);
}
printf("/n");
}
}
int min(int a, int b, int c)
{
int m = a;
if (m > b)
m = b;
if (m > c)
m = c;
return m;
}
int main()
{
bool M[R][C] = {{0, 1, 1, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0}};
printMaxSubSquare(M);
getchar();
}
這個題目可以有很多變種。
(1) The largest rectangle under a histogram
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
Given: An integer array represents a histogram
Goal: Find the largest rectangle under the histogram.
Complexity O(N) where N is the size of the given array.
輸入為一個整數數組h[i]. 對于圖中的某個面積最大的矩形，必然有一個最低的高度h[k]，即矩形的高等于 h[k]，以第k塊矩形的高度，最左邊可以到達這個矩形的左邊，最右邊可以到達這個矩形的右邊。是以，可以以每塊矩形進行擴充，求出最左邊和最右邊（即兩 邊的高度都大于等于這塊的高度），得出面積s[i]，這樣就可求出最大的s[i]了。
const int MAX = 100005;
__int64 h[MAX];
__int64 left[MAX], right[MAX]; //left[i] = j表示第i個矩形以它的高度到達最左邊的下标
void Solve ()
{
int i;
__int64 temp, max;
for (i=1; i<=n; i++)
{
left[i] = right[i] = i;
}
for (i=1; i<=n; i++)
{
while ( h[left[i]-1] >= h[i] )
left[i] = left[left[i]-1];
}
for (i=n; i>0; i--)
{
while ( h[right[i]+1] >= h[i] )
right[i] = right[right[i]+1];
}
max = 0;
for (i=1; i<=n; i++)
{
temp = h[i] * (right[i] - left[i] + 1);
if ( temp > max )
max = temp;
}
printf("%I64d/n", max);
}
(2) Maximum subarray with all 1’s. (Generalization of problem 1)
http://www.drdobbs.com/184410529
Given A two-dimensional array b (M rows, N columns) of Boolean values ("0" a
nd "1")
Goal: Find the largest (most elements) rectangular subarray containing all o
nes.
Key observation: 從一邊（假設右邊）開始逐列掃描，構造直方圖。每次構造出直方圖
來，用上面的解法求最大矩陣。每次構造直方圖隻需要O（M），解需要O（M），做N次。
Complexity O(MN).
(3) Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that a
ll four borders are filled with black pixels. (variation of problem 3)
http://careercup.com/question?id=2445
(4) Given an NxN matrix of positive and negative integers, write code to find the sub-matrix with the largest possible sum. (Kadane's 2D)
5. max min distance
給一個M個數字的從1到N的整數數組，找出一個K個大小的子集，這個子集
每個數pair的Distance，使得這個min distance 最大化。
先Sort 數組
DP方程f(k,a,b) = max{{for a<i<=b-k}min{dis(a,i), f(k-1,i,b)}}
每算一個狀态點f(k,a,b)用O(log(b-a)), 一共有O(k*n*n)個這樣的點，複雜度O(n*n*klogn)
6. 編輯距離問題
Three allowed operations: delete a character, insert a character, replace a character.
Now given two words - word1 and word2 – find the minimum number of steps required to convert word1 to word2
The following recurrence relations define the edit distance, d(s1,s2), of two strings s1 and s2:
d('', '') = 0 -- '' = empty string
d(s, '') = d('', s) = |s| -- i.e. length of s
d(s1+ch1, s2+ch2)
= min( d(s1, s2) + if ch1=ch2 then 0 else 1 fi,
d(s1+ch1, s2) + 1,
d(s1, s2+ch2) + 1 )
The first two rules above are obviously true, so it is only necessary consider the last one. Here, neither string is the empty string, so each has a last character, ch1 and ch2 respectively. Somehow, ch1 and ch2 have to be explained in an edit of s1+ch1 into s2+ch2. If ch1 equals ch2, they can be matched for no penalty, i.e. 0, and the overall edit distance is d(s1,s2). If ch1 differs from ch2, then ch1 could be changed into ch2, i.e. 1, giving an overall cost d(s1,s2)+1. Another possibility is to delete ch1 and edit s1 into s2+ch2, d(s1,s2+ch2)+1. The last possibility is to edit s1+ch1 into s2 and then insert ch2, d(s1+ch1,s2)+1. There are no other alternatives. We take the least expensive, i.e. min, of these alternatives.
The recurrence relations imply an obvious ternary-recursive routine. This is not a good idea because it is exponentially slow, and impractical for strings of more than a very few characters.
Examination of the relations reveals that d(s1,s2) depends only on d(s1',s2') where s1' is shorter than s1, or s2' is shorter than s2, or both. This allows the dynamic programming technique to be used.
A two-dimensional matrix, m[0..|s1|,0..|s2|] is used to hold the edit distance values:
m[i,j] = d(s1[1..i], s2[1..j])
m[0,0] = 0
m[i,0] = i, i=1..|s1|
m[0,j] = j, j=1..|s2|
m[i,j] = min(m[i-1,j-1]
+ if s1[i]=s2[j] then 0 else 1 fi,
m[i-1, j] + 1,
m[i, j-1] + 1 ), i=1..|s1|, j=1..|s2|
m[,] can be computed row by row. Row m[i,] depends only on row m[i-1,]. The time complexity of this algorithm is O(|s1|*|s2|). If s1 and s2 have a `similar' length, about `n' say, this complexity is O(n2), much better than exponential!
7. 求最長上升子列的長度 最長遞增序列
給定a(1..n),求最長上升子列的長度即滿足a(b(0)..b(m)),其中b(i)<b(i+1),a(b(i))<a(b(i+1))
同樣我們用DP搞定它,先是一個O(n^2)的算法
f(i):=以a(i)結尾的最大上升子列的長度. (f(1)=1)
f(i):=max{1,f(j)+1} (j=1..i-1 and a(j)<a(i))
#include <iostream>
using namespace std;
int main()
{
int i,j,n,a[100],b[100],max;
while(cin>>n)
{
for(i=0;i<n;i++)
cin>>a[i];
b[0]=1;//初始化，以a[0]結尾的最長遞增子序列長度為1
for(i=1;i<n;i++)
{
b[i]=1;//b[i]最小值為1
for(j=0;j<i;j++)
if(a[i]>a[j]&&b[j]+1>b[i])
b[i]=b[j]+1;
}
for(max=i=0;i<n;i++)//求出整個數列的最長遞增子序列的長度
if(b[i]>max)
max=b[i];
cout<<max<<endl;
}
return 0;
}
上面在狀态轉移時的複雜度為o(n),即在找a[k]前面滿足a[j]<a[k]的最大b[j]時采用的是順序查找的方法，複雜度為 o(n).設想如果能把順序查找改為折半查找，則狀态轉移時的複雜度為o(lg(n)),這個問題的總的複雜度就可以降到nlg(n). 另定義一數組c,c中元素滿足c[b[k]]=a[k],解釋一下，即當遞增子序列的長度為b[k]時子序列的末尾元素為c[b[k]]=a[k].
#include <iostream>
using namespace std;
int find(int *a,int len,int n)//若傳回值為x,則a[x]>=n>a[x-1]
{
int left=0,right=len,mid=(left+right)/2;
while(left<=right)
{
if(n>a[mid]) left=mid+1;
else if(n<a[mid]) right=mid-1;
else return mid;
mid=(left+right)/2;
}
return left;
}
void fill(int *a,int n)
{
for(int i=0;i<=n;i++)
a[i]=1000;
}
int main()
{
int max,i,j,n,a[100],b[100],c[100];
while(cin>>n)
{
fill(c,n+1);
for(i=0;i<n;i++)
cin>>a[i];
c[0]=-1;// …………………………………………1
c[1]=a[0];// ……………………………………2
b[0]=1;// …………………………………………3
for(i=1;i<n;i++)// ………………………………4
{
j=find(c,n+1,a[i]);// ……………………5
c[j]=a[i];// ………………………………6
b[i]=j;//……………………………………7
}
for(max=i=0;i<n;i++)//………………………………8
if(b[i]>max)
max=b[i];
cout<<max<<endl;
}
return 0;
}
對于這段程式，我們可以用算法導論上的loop invariants來幫助了解.
loop invariant: 1、每次循環結束後c都是單調遞增的。(這一性質決定了可以用二分查找）
2、每次循環後，c[i]總是儲存長度為i的遞增子序列的最末的元素，若長度為i的遞增子序
列有多個，剛儲存末尾元素最小的那個.（這一性質決定是第3條性質成立的前提）
3、每次循環完後，b[i]總是儲存以a[i]結尾的最長遞增子序列。
initialization: 1、進入循環之前，c[0]=-1,c[1]=a[0],c的其他元素均為1000,c是單調遞增的;
2、進入循環之前，c[1]=a[0],儲存了長度為1時的遞增序列的最末的元素，且此時長度為1
的遞增了序列隻有一個，c[1]也是最小的;
3、進入循環之前，b[0]=1，此時以a[0]結尾的最長遞增子序列的長度為1.
maintenance: 1、若在第n次循環之前c是單調遞增的，則第n次循環時，c的值隻在第6行發生變化，而由
c進入循環前單調遞增及find函數的性質可知（見find的注釋),
此時c[j+1]>c[j]>=a[i]>c[j-1],是以把c[j]的值更新為a[i]後，c[j+1]>c[j]>c[j-1]的性質仍然成
立，即c仍然是單調遞增的；
2、循環中，c的值隻在第6行發生變化，由c[j]>=a[i]可知，c[j]更新為a[i]後，c[j]的值隻會變
小不會變大，因為進入循環前c[j]的值是最小的，則循環中把c[j]更新為更小的a[i]，當
然此時c[j]的值仍是最小的;
3、循環中，b[i]的值在第7行發生了變化，因為有loop invariant的性質2，find函數傳回值
為j有：c[j-1]<a[i]<=c[j],這說明c[j-1]是小于a[i]的，且以c[j-1]結尾的遞增子序列有最大的
長度，即為j-1,把a[i]接在c[j-1]後可得到以a[i]結尾的最長遞增子序列，長度為(j-1)+1=j;
termination: 循環完後，i=n-1,b[0],b[1],...,b[n-1]的值均已求出，即以a[0],a[1],...,a[n-1]結尾的最長遞
增子序列的長度均已求出，再通過第8行的循環，即求出了整個數組的最長遞增子序列。
仔細分析上面的代碼可以發現，每次循環結束後，假設已經求出c[1],c[2],c[3],...,c[len]的值，則此時最長遞增子序列的長度為len,是以可以把上面的代碼更加簡化，即可以不需要數組b來輔助存儲，第8行的循環也可以省略。
#include <iostream>
using namespace std;
int find(int *a,int len,int n)//修改後的二分查找，若傳回值為x，則a[x]>=n
{
int left=0,right=len,mid=(left+right)/2;
while(left<=right)
{
if(n>a[mid]) left=mid+1;
else if(n<a[mid]) right=mid-1;
else return mid;
mid=(left+right)/2;
}
return left;
}
int main()
{
int n,a[100],c[100],i,j,len;//新開一變量len,用來儲存每次循環結束後c中已經求出值的元素的最大下标
while(cin>>n)
{
for(i=0;i<n;i++)
cin>>a[i];
b[0]=1;
c[0]=-1;
c[1]=a[0];
len=1;//此時隻有c[1]求出來，最長遞增子序列的長度為1.
for(i=1;i<n;i++)
{
j=find(c,len,a[i]);
c[j]=a[i];
if(j>len)//要更新len,另外補充一點：由二分查找可知j隻可能比len大1
len=j;//更新len
}
cout<<len<<endl;
}
return 0;
}
8. 最大公共子串問題
int commstr(char *str1, char *str2)
{
int len1=strlen(str1),len2=strlen(str2),row,col,max=0;
int **pf = new int*[len1+1];//動态配置設定一個二維數組作為輔助空間
for (row=0; row<len1+1; row++)
pf[row] = new int[len2+1];
//數組賦初值
for (row=0; row<len1+1; row++)
pf[row][0] = 0;
for (col=0; col<len2+1; col++)
pf[0][col] = 0;
for (row=1; row<=len1; row++)
for (col=1;col<=len2; col++)
{
if (str1[row-1] == str2[col-1])
{
pf[row][col] = pf[row-1][col-1] + 1;
max = pf[row][col] > max ? pf[row][col] : max;
}
else
pf[row][col] = 0;
}
//空間回收
for (row=0; row<len1+1; row++)
delete[] pf[row];
delete[] pf;
return max;
}
上面這個DP還好了解吧，但是複雜度相當高O(MN)，串長時空間複雜度也很高。如果涉及到多個字元串求公共子串複雜度更是不得了，這時候要使用廣 義字尾樹（Generalized Suffix Tree，簡稱GST)算法，就是把給定的N個源字元串的所有的字尾建成一顆樹，這個樹有以下一些特點：
1.樹的每個節點是一個字元串，樹根是空字元串“”
2.任意一個字尾子串都可以由一條從根開始的路徑表達
（将這條路徑上的節點字元串依次拼接起來就可以得到這個字尾）
3.特别應注意任意一個子串都可以看作某一個字尾的字首。既然每一個字尾 都可以由一條從根開始的路徑表達，那麼我們可以從根節點開始一個字元 一個字元的跟蹤這條路徑進而得到任意一個子串。
4.為了滿足查找公共子串的需求，每個節點還應該有從屬于哪個源字元串的 資訊
由以上的定義我們不難看出，在這棵GST樹上，如果找到深度最大并且從屬于所有字串的節點，那麼，把從根到這個節點的路徑上的所有節點字元串拼接起來就是LCS。
還是舉例說明，上面提到的三個字元串【abcde cdef ccde】的所有字尾子串清單如
下：
(注：.1表示是從第一個串abcde來的，同理.2,.3分别表示從cdef，ccde來的)
abcde.1
bcde.1
cde.1
de.1
e.1
cdef.2
def.2
ef.2
f.2
ccde.3
cde.3
de.3
e.3
建成的GST如下圖所示
(注:.1表示從屬于第一個串，.123表示既從屬于第一又從屬于第二，第三個源串）
--/_______【abcde.1】
|
|_____【bcde.1】 .....最深的并且帶.123的節點
| :
|_____【c.123】____【de.123】_______【f.2】
| |
| |__【cde.3】
|
|_____【de.123】___【f.2】
|
|_____【e.123】____【f.2】
|
|_____【f.2】
上圖中虛線所指的【de.123】節點所表示的子串cde正是LCS
以上是一些基本概念，但是實際應用時還要涉及到建構GST樹以及查找LCS的具體算法，基本上可以以O(n)的時間複雜度進行建樹及查找處理。
9. 背包問題
10. 正則比對
KMP算法才是王道，不過，如果隻比對*和?，可以這樣
規定x[i]表示字元串x的第i個字元，注意，這裡的下标從1開始。定義一個函數Match[i, j]，表示特征串x的長度為i的字首與字元串的s的長度為j的字首是否比對。經過分析可以寫出如下的遞歸公式：
Match[i,j] = Match[i-1, j-1], if x[i] = ’?’
= Match[i-1, 1..j]中任何一個等于true, if x[i]=’*’
= Match[i-1, j-1] and (x[i] = s[j]), if x[i]不是通配符
該遞歸公式的邊界條件是
Match[0,0] = true,
Match[i,0] = Match[i-1,0], if x[i] = ’*’
= false, otherwise
根據上面的遞歸公式和邊界條件，很容易寫出一個動态規劃算法來判斷正規表達式x是否比對字元串s。這個算法的複雜度是O(mn)
11.最短路徑
12. 劃分問題
[問題]Given an array of "n" random integers and an integer k<=n. Find the k
numbers such that the minimum difference of all the possible pairs of k
numbers is maximized (maximum among other minimum differences for various
possible selections of k numbers).
首先兩頭的點是必須找的，中間還需要k-2個點。
令1~n閉區間内k個數的最大最小差為f(1, n, k)，假設第二個點位于i處
f(1, n, k) = max(2<=i<=n+2-k) min{f(1, i, 2), f(i, n, k-1)}
f(x, y, 2) = a[y]-a[x]
[問題]max-mindist: 一個數組有n個元素全是正數，把這個數組分成非空的k段，每段都連續。求最每段元素
和的最大值的最小值。
令1~n閉區間分成n段的最小最大和為f(1, n, k)，假設第一段為1~i
f(1, n, k) = min(1<=i<=n+1-k) max{f(1, i, 1), f(i+1, n, k-1)}
f(x, y, 1) = a[x]+a[x+1]+...+a[y]
f(k,head,end) = max_{for i in head+1, end-k}min{dis(head,i), f(k-1,i,end)}
![在DOS下運作不了ipconfig指令[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)