身份证和学生卡一起弄丢了,我擦,真蛋疼
这道题是算法导论15章第二题,求最长回文子串
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
|
#include<string.h> #include<stdlib.h> #define MAXLEN 50 int (char str[],int n) { int dp[n][n]; memset(dp,0,sizeof(dp)); for(int i = 0; i < n;i++) { dp[i][i] = 1; } for(int len = 2 ; len <= n; len++) for(int j = 0 ; j < n - len + 1; j++) { if(str[j] == str[j + len - 1]) { dp[j][j + len - 1] = dp[j + 1][j + len - 2] + 2; } else { dp[j][j + len - 1] = dp[j + 1][j + len - 1] > dp[j][j + len - 2]?dp[j + 1][j + len - 1]:dp[j][j + len - 2]; } } return dp[0][n - 1]; } int main() { char str[MAXLEN]; printf("please input your string and press entern"); gets(str); int res = palindrome(str,strlen(str)); printf("%dn",res); return 0; }
|
这是我的原始代码
思路是dp,dp[i][i] = 1,dp[i]j = dp[i] == dp[j] ? dp[i + 1][j - 1] : max{dp[i][j-1],dp[i-1][j]}
近期评论