(1)、問(wèn)題描述：給出2個(gè)序列，x是從1到m，y是從1到n，找出x和y的最長(zhǎng)公共子序列？

成都創(chuàng)新互聯(lián)公司主營(yíng)延川網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,成都App定制開(kāi)發(fā),延川h5小程序制作搭建,延川網(wǎng)站營(yíng)銷推廣歡迎延川等地區(qū)企業(yè)咨詢

x：A B C B D A B

y：B D C A B A

則：最長(zhǎng)公共子序列長(zhǎng)度為4，BDAB BCAB BCBA均為L(zhǎng)CS(最長(zhǎng)公共子序列)；

模型實(shí)現(xiàn)圖：

(2)、問(wèn)題解決

  代碼實(shí)現(xiàn)了最長(zhǎng)公共子序列的長(zhǎng)度

#include

#define N    10

int LCS(int *a, int count1, int *b, int count2);
int LCS(int *a, int count1, int *b, int count2){
    int table[N][N] = {0};
    int i;
    int j;

    for(i = 0; i < count1; i++){
        for(j = 0; j < count2; j++){
            if(a[i] == b[j]){
                table[i+1][j+1] = table[i][j]+1;
            }else{
                table[i+1][j+1] = table[i+1][j] > table[i][j+1] ? table[i+1][j] : table[i][j+1];
            }
        }
    }

    return table[count1][count2];
}

void main(void){
    int a[] = {1, 2, 3, 4, 5, 6};
    int b[] = {2, 3, 5, 6, 7};
    int count1 = sizeof(a)/sizeof(int);
    int count2 = sizeof(b)/sizeof(int);
    int number;

    number = LCS(a, count1, b, count2);
    printf("%d\n", number);
}

  結(jié)果截圖

(3)、動(dòng)態(tài)規(guī)劃的特征：

  特征一(最優(yōu)子結(jié)構(gòu)的性質(zhì))：一個(gè)問(wèn)題的最優(yōu)解包含了子問(wèn)題的最優(yōu)解；

  特征二：重疊子問(wèn)題，一個(gè)遞歸的過(guò)程包含很少的獨(dú)立子問(wèn)題被反復(fù)計(jì)算了多次；

  時(shí)間復(fù)雜度：O(m*n)；