LeetCode刷题复盘笔记 |
您所在的位置:网站首页 › 动态规划算法和递归算法区别是什么 › LeetCode刷题复盘笔记 |
今日主要总结一下动态规划的一道题目,647. 回文子串 题目:647. 回文子串[Leetcode题目地址](扣) 题目描述: 给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。 示例 1: 输入:s = "abc" 输出:3 解释:三个回文子串: "a", "b", "c" 示例 2: 输入:s = "aaa" 输出:6 解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa" 提示: 1 我们在判断字符串S是否是回文,那么如果我们知道 s[1],s[2],s[3] 这个子串是回文的,那么只需要比较 s[0]和s[4]这两个元素是否相同,如果相同的话,这个字符串s 就是回文串。 那么此时我们是不是能找到一种递归关系,也就是判断一个子字符串(字符串的下表范围[i,j])是否回文,依赖于,子字符串(下表范围[i + 1, j - 1])) 是否是回文。 所以为了明确这种递归关系,我们的dp数组是要定义成一位二维dp数组。 布尔类型的dp[i][j]:表示区间范围[i,j] (注意是左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false。 2. 确定递推公式 在确定递推公式时,就要分析如下几种情况。 整体上是两种,就是s[i]与s[j]相等,s[i]与s[j]不相等这两种。 当s[i]与s[j]不相等,那没啥好说的了,dp[i][j]一定是false。 当s[i]与s[j]相等时,这就复杂一些了,有如下三种情况 情况一:下标i 与 j相同,同一个字符例如a,当然是回文子串 情况二:下标i 与 j相差为1,例如aa,也是回文子串 情况三:下标:i 与 j相差大于1的时候,例如cabac,此时s[i]与s[j]已经相同了,我们看i到j区间是不是回文子串就看aba是不是回文就可以了,那么aba的区间就是 i+1 与 j-1区间,这个区间是不是回文就看dp[i + 1][j - 1]是否为true。 以上三种情况分析完了,那么递归公式如下: if (s[i] == s[j]) { if (j - i如果这矩阵是从上到下,从左到右遍历,那么会用到没有计算过的dp[i + 1][j - 1],也就是根据不确定是不是回文的区间[i+1,j-1],来判断了[i,j]是不是回文,那结果一定是不对的。 所以一定要从下到上,从左到右遍历,这样保证dp[i + 1][j - 1]都是经过计算的。 有的代码实现是优先遍历列,然后遍历行,其实也是一个道理,都是为了保证dp[i + 1][j - 1]都是经过计算的。 代码如下: for (int i = s.size() - 1; i >= 0; i--) { // 注意遍历顺序 for (int j = i; j = 0; i--){ for(int j = i; j |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |