萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣516题-最长回文子序列-动态规划题解

发表于 2021-04-18 | 分类于 力扣刷题 | 0 | 阅读次数 301

题目描述

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

样例

  1. 示例 1:
    输入:"bbbab"
    输出:4
    一个可能的最长回文子序列为 "bbbb"。

  2. 示例 2:
    输入:"cbbd"
    输出:2
    一个可能的最长回文子序列为 "bb"。

题目评估

知识点:动态规划
难度:中等

分析

利用动态规划解题有以下四个步骤:

  1. 确定状态
    我们可以开辟一个二维数组dp[i][j]表示从 i 到 j 子串的最长回文子序列的长度。

  2. 转移方程
    我们可以发现,如果子串s[i..j]的两头字符s[i]和s[j]如果相等,那么s[i..j]的子串s[i+1..j-1]的最长回文子序列的长度+2后的值其实就是s[i..j]的最长回文子序列的长度,即dp[i][j] = dp[i+1][j-1] + 2。
    但是,如果子串s[i..j]的两头字符s[i]和s[j]如果不相等,那么我们就取子串s[i+1..j]和s[i..j-1]两者中最长回文子序列长度最大的一个值赋给s[i..j]的最长回文子序列长度,即dp[i][j] = max( dp[i+1][j] , dp[i][j-1] )。

  3. 初始条件和边界情况
    我们要知道,每个字符其实都是长度为1的回文子序列,所以dp[i][i]的值应该为1,然后i < j,但是在i > j的数组区域应该把所有值赋为0(java初始化就是0),因为当一个长度为2的串取子串dp[i+1][j-1]的时候i的值就会大于j,这时取到的值应该为0,而不是未定义。

  4. 计算顺序
    从整体来看,我们要从后往前计算,所有子串的头i应该从后往前移动,子串的尾应该从i + 1开始往后移动。

  • 下图中黑色箭头代表复制值,红色箭头代表+2

leetcode-516-Dynamic programming analysis chart

Java代码题解

public class Main {
	public static void main(String[] args) {
		Solution s = new Solution();
		int res = s.longestPalindromeSubseq("qwafceah");
		System.out.println(res);
	}
}

class Solution {
    public int longestPalindromeSubseq(String s) {
		
    	// 定义一个字符串长度*字符串长度的二维数组,用来保存子串的最大回文子序列长度
    	int[][] dp = new int[s.length()][s.length()];
    	
    	for (int i = dp.length - 1; i >= 0; i--) {        // i从最后一个开始遍历
			dp[i][i] = 1;  // 初始化,每个字符都是长度为一的回文
    		for (int j = i + 1; j < dp[i].length; j++) {  // j从第i+1个开始遍历
				if (s.charAt(i) == s.charAt(j)) {  // 如果子串的两头字符相等
					// 该子串掐掉两头后的子串最大子回文序列长度+2就是该子串的最大回文子序列长度
					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][dp[0].length - 1];
    }
}
力扣516题

复杂度分析

设n表示字符串长度,双层遍历一个二维数组,时间复杂度为O(n^2)
开辟了一个n*n的二维数组,空间复杂度为O(n^2)

# 算法 # 程序设计 # 动态规划
力扣1143题-最长公共子序列-题解
力扣1312题-让字符串成为回文串的最少插入次数-动态规划题解
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

77 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持