汉南城乡建设局网站,易企秀h5制作官网,wordpress完整中文免费主题下载,wordpress回复一句话总结#xff1a;最关键的是dp数组的定义。 原题链接#xff1a;647 回文子串 按动规五部曲一步步进行分析#xff1a;
dp数组及其下标的定义#xff1a;首先需要确定为二维数组#xff0c;其中dp[i][j]表示区间[i, j]之中的子串是否为回文子串#xff1b;状态转移…一句话总结最关键的是dp数组的定义。 原题链接647 回文子串 按动规五部曲一步步进行分析
dp数组及其下标的定义首先需要确定为二维数组其中dp[i][j]表示区间[i, j]之中的子串是否为回文子串状态转移方程如果s[i] s[j]那么区间[i, j]之中的子串是否为回文子串还依赖于[i 1, j - 1]之间的状态是否为true即有 if (s[i] s[j] (dp[i 1][j -1] || j - i 1)) {dp[i][j] true;}如果s[i] ! s[j]那么肯定dp[i][j]肯定就是false了状态方程的初始化很明显对于每个单个的字符都是一个回文串因此有dp[i][i] true方程的遍历顺序从状态转移方程可以看出dp[i][j]的计算依赖于dp[i 1][j - 1]因此对i的遍历需要从后往前对j的计算需要从前往后举例推导dp数组。
最终代码如下
class Solution {public int countSubstrings(String s) {int n s.length();char[] cs s.toCharArray();boolean[][] dp new boolean[n][n];int ans 0;for (int i n - 1; i 0; --i) {for (int j i; j n; j) {if (cs[i] cs[j] (j - i 1 || dp[i 1][j - 1])) {ans;dp[i][j] true;} }}return ans;}
} 原题链接516 最长回文子序列 dp五部曲分析如下
dp数组及其下标的确定dp[i][j]表示区间[i, j]之中的最长回文子序列的长度状态转移方程的推导当s[i] s[j]时有dp[i][j] dp[i 1][j - 1] 2当s[i] ! s[j]时则有dp[i][j] Math.max(dp[i][j - 1], dp[i 1][j]) 类似于上题dp[i][i] 1类似于上题i的遍历从后往前j的遍历从前往后由i开始举例推导dp数组略。
最终代码如下
class Solution {public int longestPalindromeSubseq(String s) {int n s.length();char[] cs s.toCharArray();int[][] dp new int[n][n];for (int i 0; i n; i) dp[i][i] 1;for (int i n - 1; i 0; --i) {for (int j i 1; j n; j) {if (cs[i] cs[j]) dp[i][j] dp[i 1][j - 1] 2;else dp[i][j] Math.max(dp[i][j - 1], dp[i 1][j]);}}return dp[0][n - 1];}
}
