动态规划之最长子序列长LCS

2019-11-06 07:16:12

字体：大中小

来源：转载

供稿：网友

#include <iostream> #include <stdio.h>#include <assert.h>#include <stdlib.h>#include <String.h>#define MAXLENGTH 1000using namespace std;int a[MAXLENGTH][MAXLENGTH];void LCS_LENGTH(char x[], char y[], int x_length, int y_length){ memset(a, MAXLENGTH*MAXLENGTH, sizeof(int)); for(int i=0; i<=x_length; i++){ a[i][0] = 0; } for(int j=0; j<=y_length; j++){ a[0][j] = 0; } for(int i=1; i<=x_length; i++){ for(int j=1; j<=y_length; j++){ if(x[i-1] == y[j-1]){ a[i][j] = a[i-1][j-1] +1; // b[i][j] = ''; }else{ a[i][j] = a[i][j-1]>=a[i-1][j] ? a[i][j-1] : a[i-1][j]; } } } for(int i=0; i<=x_length; i++){ for(int j=0; j<=y_length; j++){ cout << a[i][j]; } cout<<endl; } return;} int main(){ char x[MAXLENGTH], y[MAXLENGTH]; while(cin >>x >>y){ LCS_LENGTH(x, y, strlen(x), strlen(y)); } return 0;}

上一篇：1098.Insertion or Heap Sort (25)

下一篇：玲珑学院OJ 1097 萌萌哒的第二题【dp+线段树】