代码随想录训练营第五十七天|647. 回文子串、516.最长回文子序列

 647. 回文子串

题目链接/文章讲解/视频讲解：代码随想录

1.代码展示

//647.回文子串
int countSubstrings(string s) {
	//step1 构建dp数组，明确dp数组的含义，dp[i][j]的含义是在下标为i和j区间内的字串是否为回文串
	vectorbool>> dp(s.size(), vector<bool>(s.size(), false));
	//step2 构建状态转移方程
	//当s[i] != s[j]时，此时必定不为回文子串
	//当s[i] == s[j]时，有三种情况
	//情况一：i = j，此时就是本身，因此必定为回文子串
	//情况二：i + 1 = j，此时就如aa的形式，因此也是回文子串
	//情况三：j > i + 1，此时当dp[i + 1][j - 1]为回文字串时，dp[i][j]才是回文子串
	//step3 初始化dp数组，都为false
	//step4 开始遍历
	int nResult = 0;
	for (int i = s.size() - 1; i >= 0; i++) {
		for (int j = i; j < s.size(); j++) {
			if (s[i] == s[j]) {
				if (j - i <= 1) {
					nResult++;
					dp[i][j] = true;
				}
				else if (dp[i + 1][j - 1]){
					nResult++;
					dp[i][j] = true;
				}
			}
		}
	}
	return nResult;
}

 2.本题小节

        思考：本题的重点在于对于dp[i][j]的理解，dp[i][j]的含义是在下标为i和j区间内的字串是否为回文串。构建状态转移方程，当s[i] != s[j]时，此时必定不为回文子串；当s[i] == s[j]时，有三种情况
 ，情况一，i = j，此时就是本身，因此必定为回文子串， 情况二，i + 1 = j，此时就如aa的形式，因此也是回文子串，情况三：j > i + 1，此时当dp[i + 1][j - 1]为回文字串时，dp[i][j]才是回文子串；初始化都为false，最后注意遍历顺序，先下后上，先左后右。

        基本思路：注意理解dp[i][j]的含义，按照代码的思路来即可。

516.最长回文子序列

题目链接/文章讲解/视频讲解：代码随想录

1.代码展示

//516.最长回文子序列
int longestPalindromeSubseq(string s) {
	//step1 构建dp数组，dp[i][j]的含义是在[i,j]下标的范围内s的最长回文子序列
	vectorint>> dp(s.size(), vector<int>(s.size(), 0));
	//step2 状态转移方程
	//当s[i] == s[j]，dp[i][j] = dp[i + 1][j - 1] + 2，
	//不等时，有两种情况，说明同时加入s[i],s[j]不能满足情况，分别加入s[i]和s[j]试试
	//则dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
	//step3 初始化
	for (int i = 0; i < s.size(); i++) {
		dp[i][i] = 1;
	}
	//step4 开始遍历
	for (int i = s.size() - 1; i >= 0; i++) {
		for (int j = i + 1; j < s.size(); j++) {
			if (s[i] == s[j]) {
				dp[i][j] = dp[i + 1][j - 1] + 2;
			}
			else {
				dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
			}
		}
	}
	return dp[0][s.size() - 1];
}

 2.本题小节

        思考：明确dp数组的含义。dp[i][j]的含义是在[i,j]下标的范围内s的最长回文子序列。状态转移方程，当s[i] == s[j]，dp[i][j] = dp[i + 1][j - 1] + 2，不等时，有两种情况，说明同时加入s[i],s[j]不能满足情况，分别加入s[i]和s[j]试试，则dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])，初始化时对角线都为1，根据dp数组可以得。遍历时先下后上，先左后右。

        基本思路：注意dp数组的含义，按照动态规划步骤来。

动态规划总结：代码随想录