动态规划一、问题描述用 动 态 规 划 法 求 两 个 字 符 串 A=‘xzyzzyx’ 和B=‘zxyyzxz’的最长公共子序列二、算法分析(1)、若 xm=yn,则 zk=xm=yn，且 Zk-1 是 Xm-1 和 Yn-1 的最长公共自序列；(2)、若 xm≠yn,且 zk≠xm，则 Zk 是 Xm-1 和 Yn 的最长公共自序列；(3)、若 xm≠yn,且 zk≠yn，则 Zk 是 Xm 和 Yn-1 的最长公共自序列；设 L(m,n)表示序列 X={x1,x2,…,xm}和 Y={y1,y2,…,yn}的最长公共子序列的长度L 表示已经决策的长度S 表示每个决策的状态L(0,0)=L(0,j)=0 1≤i≤m, 1≤j≤n L(i-1,j-1)+1 xi=yi,i≥1,j≥1L(i,j)= max{L(i,j-1),(L(i-1,j)} xi≠yi,i≥1,j≥1 1 xi=yiS(i,j)= 2 xi≠yi 且 L(i,j-1)≥L(i-1,j) 3 xi≠yi 且 L(i,j-1)< L(i-1,j) xzyzzyx00000000z00111111x01111222y01122222y01122333z01122334x01123334z01223344长度矩阵 L三、源代码#include #include using namespace std; int main() { string str1 = "xzyzzyx"; string str2 = "zxyyzxz"; int x_len = (); int y_len = (); int arr[50][50] ={{0,0}}; int i = 0; int j = 0; for(i = 1; i <= x_len; i++) { for(j = 1; j <= y_len; j++) { if(str1[i - 1] == str2[j - 1]) { arr[i][j] = arr[i - 1][j - 1] + 1; } else if(arr[i][j - 1] >= arr[i - 1][j]) arr[i][j] = arr[i][j - 1]; else arr[i][j] = arr[i -1][j]; } } for(i = 0 ; i <= x_len; i++) { for( j = 0; j <= y_len; j++) { cout << arr[i][j] << " "; } cout << endl; } for(i = x_len, j = y_len; i >= 1 && j >= 1;) { if(str1[i - 1] == str2[j - 1]) { cout << str1[i - 1] << " "; i--; j--; } else if(arr[i][j -1] > arr[i - 1][j]) j--; else i--; } cout << endl; return 0; }
