1143.|1143. 最长公共子序列/5. 最长回文子串 1143.最长公共子序列

1143. 最长公共子序列

相关标签： DP

#define BUFLEN 1001 #define MAX(x,y) (x > y ? x : y) int longestCommonSubsequence(char * text1, char * text2){int dp[BUFLEN][BUFLEN] = {0}; int res = 0; for (int i = 0; i < strlen(text1); i++) { for (int j = 0; j < strlen(text2); j++) {dp[i + 1][j + 1] = (text1[i] == text2[j]) ? dp[i][j] + 1 : MAX(dp[i][j + 1], dp[i + 1][j]); } }return dp[strlen(text1)][strlen(text2)]; }

5. 最长回文子串

相关标签：DP

/* 1. N * ( 双指针两边拓展)2. 正，反-》最长公共子串-》 DPdp[i][j] = dp[i-1][j-1] + 1不对回文不一样。。 dp[i][j] 表示 i..j 是不是回文 -- 》dp[i+1][j-1] 是不是回文*/// #define R(idx, len) (len - 1 - idx)// reverse #define BUFLEN 1001 char * longestPalindrome(char * s){if (strlen(s) == 0 || strlen(s) == 1) { return s; }int dp[BUFLEN][BUFLEN] = {0}; int maxi = 0; int max = 0; for (int j = 0; j < strlen(s); j++) { for (int i = 0; i <= j ; i++) { dp[i + 1][j +1] = (s[i] == s[j]) && (j - i <= 2|| dp[i+2][j]); if (dp[i + 1][j +1] && j - i >= max) { max = j - i + 1; maxi = i; }} }// for (int i = 0; i <= strlen(s); i++) { // for (int j = 0; j <= strlen(s); j++) { //printf("%d ", dp[i][j]); // } // printf("\n"); // }printf("%d %d\n", maxi, max); char *res = (char *)malloc(max + 1); // “\0” max + 1 memset(res, 0, max + 1); memcpy(res, &s[maxi], max); return res; }