代码随想录算法训练营 Day46 动态规划ⅩⅢ 回文字符串

发布于：2025-05-18 ⋅ 阅读:(20) ⋅ 点赞:(0)

动态规划

动态规划回顾

动规五部曲分别为：

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

动规五部曲里，哪一部没想清楚，这道题目基本就做不出来，即使做出来了也没有想清楚，而是朦朦胧胧的就把题目过了。

  • 如果想不清楚dp数组的具体含义，递归公式从何谈起，甚至初始化的时候就写错了。
  • 例如动态规划：不同路径还不够，要有障碍！ (opens new window)在这道题目中，初始化才是重头戏
  • 如果看过背包系列，特别是完全背包，那么两层for循环先后顺序绝对可以搞懵很多人，反而递归公式是简单的。
  • 至于推导dp数组的重要性，动规专题里几乎每篇Carl都反复强调，当程序结果不对的时候，一定要自己推导公式，看看和程序打印的日志是否一样。

动态规划基础

背包问题系列

打家劫舍系列

股票系列

在这里插入图片描述

子序列系列

在这里插入图片描述

题目

647. 回文子串 - 力扣（LeetCode）
回文串中间开始左右两边对称，求多少字串是回文的，难点是找到 dp 数组定义
1. Dp 数组定义为 dp[i][j] 从 i 到 j 之间的字符串是否是回文的，其中 j>=i
这样只需要比较两边是否相同，能利用之前的判断结果直接判断是否回文
2. 递推公式判断两边的公式
三种情况一个元素的时候，两个元素的时候，大于两个元素的时候 dp[i+1][j-1]
if (s[i] == s[j])
情况 12发现一个回文结果++ If (j-i<=1) dp[i][j]=true; res++;
情况 3 else if (dp[i+1][j-1] == ture) dp[i][j]=true; res++}
3. 初始化 dp 为 false，通过计算统计回文字串，因此 if匹配不相等不用操作就行
4. 遍历顺序是重点，依赖于 dp[i+1][j-1] 因此遍历顺序是从下往上，左往右递推
5. 打印 dp

int countSubstrings(string s) {
	// 定义dp数组 i到j是否为回文串
	std::vector<std::vector<bool>> dp(s.size(), std::vector<bool>(s.size(), false));
	// 回文串结果
	int res = 0;
	// 遍历dp数组
	for (int i = s.size()-1; i >= 0; --i) {
		// j >= i
		for (int j = i; j <= s.size(); ++j) {
			// 递推公式
			if (s[i] == s[j]) {
				// 单个字符 或 两个字符 均是
				if (j - i <= 1) {
					dp[i][j] = true;
					res++;
				}
				// 使用之前的记录
				else if (dp[i+1][j-1]) {
					dp[i][j] = true;
					res++;
				}
			}
		}
	}
	return res;
}

516. 最长回文子序列 - 力扣（LeetCode）
回文子序列不连续
不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个回文字串。
1. dp[i][j] 定义，字符 s 中 i 到 j 区间内的子串的回文子序列的最大值
2. 递推公式，类似上一题，从中间往两边扩展
|-----| 两边相等则回文子序列在上一级基础上 dp[i+1][j-1] +2
不相等分别屏蔽左右两边
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])
3. 初始化基于 i-1 j-1
那么递推到最中间的情况 i == j相同 指向一个元素 dp[i][j]=1 单个字符是回文串
因此初始化按照如下所示
4. 遍历顺序从下往上，左往右遍历，最后元素的结果在 dp[0][s.size()-1]
5. 打印 dp

int longestPalindromeSubseq(string s) {
	// 定义dp数组 i到j之间子串的最长回文子序列
	std::vector<std::vector<int>> dp(s.size(), std::vector<int>(s.size(), 0));
	// 初始化dp数组
	for (int i = 0; i < s.size(); ++i) dp[i][i] = 1;
	// 遍历dp数组
	for (int i = s.size()-1; i >= 0; --i) {
		// j = 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] = std::max(dp[i+1][j], dp[i][j-1]);
		}
	}
	return dp[0][s.size()-1];
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布