最长公共子序列
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<time.h> 4 #include<string.h> 5 6 #define N 5 7 8 int max(int a, int b, int c) { 9 10 int ab = a>b ? a : b; 11 return ab > c ? ab : c; 12 13 } 14 15 void solve(int *array1, int *array2, int n) { 16 n = n + 1; 17 18 int *pre = (int *)malloc(n * n * sizeof(int)); 19 int *dp = (int *)malloc(n * n * sizeof(int)); 20 int i; 21 int j; 22 int a, b, c; 23 24 bzero((void *)dp, n * n * sizeof(int)); 25 bzero((void *)pre, n * n * sizeof(int)); 26 27 for(i = 1; i < n; i++) { 28 for(j = 1; j < n; j++) { 29 a = *(dp + (i -1)*n + j); 30 b = *(dp + i * n + j - 1); 31 c = *(array1 + j - 1) == *(array2 + i - 1) ? *(dp + (i -1)*n + j - 1) + 1 : *(dp + (i -1)*n + j - 1); 32 *(dp + i * n + j) = max(a, b, c); 33 } 34 } 35 36 for(i = 0; i < n; i++) { 37 for(j = 0; j < n; j++) { 38 printf("%d ", *(dp + i * n + j)); 39 } 40 printf(" "); 41 } 42 43 free(dp); 44 free(pre); 45 } 46 47 int main(char ** args) { 48 srand((unsigned)time(NULL)); 49 50 int *array1 = (int *)malloc(N * sizeof(int)); 51 for(int i = 0; i < N; i++) { 52 *(array1 + i) = rand() % N; 53 printf("%d ", *(array1 + i)); 54 } 55 printf(" "); 56 57 int *array2 = (int *)malloc(N * sizeof(int)); 58 for(int i = 0; i < N; i++) { 59 *(array2 + i) = rand() % N; 60 printf("%d ", *(array2 + i)); 61 } 62 63 printf(" "); 64 printf(" "); 65 66 solve(array1, array2, N); 67 68 free(array1); 69 free(array2); 70 return 0; 71 }