Frank's 資訊科技潮流站

動態規劃

1. 大問題可以分解為子問題

2. 每一個子問題的答案可以被儲存起來 供下次直接取用 不必再重新計算

範例：

Longest sub sequence

1. 輸入兩個sequence

2. 兩個sequence最前面留一格空格

3. 將其中一個sequence作為行的header 另一個sequence作為列的header 形成一個二維陣列 這兩個sequence的長度包含之前所補的空格後 分別為m和n m是column的長度 n是row的長度

4. 將該陣列（column,row）中的（0，0~n)和（0~m，0)均填入0 其中

5. 逐row填表，從左到右依據以下的規則填表

    如果 該 row的字元和該column的字元相同，則該格填入該 row-1,column-1 裡面的數字 +1

   如果不同，則選擇該 row-1 與 column-1 兩者之中數字較小者

6. 設有兩個sequence分別為ABCBDAB和BDCABA，則填完表格結果如下

  < A B C B D A B
> 0 0 0 0 0 0 0 0
B 0 0 1 1 1 1 1 1
D 0 0 1 1 1 2 2 2
C 0 0 1 2 2 2 2 2
A 0 1 1 2 2 2 3 3
B 0 1 2 2 3 3 3 4
A 0 1 2 2 3 3 4 4

其中

第一次令我們填出 1 的字元是 B

第一次令我們填出 2 的字元是 D

第一次令我們填出 3 的字元是 A

第一次令我們填出 4 的字元是 B

因此最長的sub sequence是 BDAB，長度是 4

C 語言範例如下

#include<stdio.h>
#include<stdlib.h>

int main(){

char a[9]={'<','A','B','C','B','D','A','B'};
char b[8]={'>','B','D','C','A','B','A'};
int mat[9][8];

for(int x=0;x<9;x++)for(int y=0;y<8;y++) mat[y][x]=0;

for(int y=1;y<7;y++){
for(int x=1;x<8;x++){
if(a[x]==b[y])mat[y][x]=mat[y-1][x-1]+1;
else{
if(mat[y-1][x]>mat[y][x-1])mat[y][x]=mat[y-1][x];
else mat[y][x]=mat[y][x-1];
}
}
}

printf(" ");

for(int g=0;g<8;g++) printf("%c ",a[g]);
printf("\n");
for(int y=0;y<7;y++){
printf("%c ",b[y]);
for(int x=0;x<8;x++){
printf("%d ",mat[y][x]);
}
printf("\n");
}

system("pause");
return 0;
}