@ 代码随想录算法训练营第8周（C语言）|Day60（动态规划）

Day60、动态规划（包含题目 ● 647. 回文子串 ● 516.最长回文子序列 ）

647. 回文子串

题目描述

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

题目解答

int countSubstrings(char* s) {int s1=strlen(s);int dp[s1][s1];int res;res=0;memset(dp,0,sizeof(dp));for(int i=s1-1;i>=0;i--){for(int j=i;j<s1;j++){if(s[i]==s[j]){if(j-i<=1){dp[i][j]=1;res++;}else{if(dp[i+1][j-1]==1){dp[i][j]=1;res++;}}}}}return res;
}

题目总结

dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。看似是一个字符串，其实要比较两头，还是两个字符串。

516.最长回文子序列

题目描述

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

题目解答

int longestPalindromeSubseq(char* s) {int s1=strlen(s);int dp[s1][s1];memset(dp,0,sizeof(dp));for(int i=0;i<s1;i++){dp[i][i]=1;}for(int i=s1-1;i>=0;i--){for(int j=i+1;j<s1;j++){if(s[i]==s[j]){dp[i][j]=dp[i+1][j-1]+2;}else{dp[i][j]=fmax(dp[i+1][j],dp[i][j-1]);}}}return dp[0][s1-1];
}

题目总结

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。