当前位置： 首页 > news >正文

大淘客网站建设,鞍山一地发布最新通知,网站优化推广方法,北京两区建设在哪里5.4 MySQL死锁了#xff0c;怎么办#xff1f; RR隔离级别下#xff0c;会存在幻读的问题#xff0c;InnoDB为了解决RR隔离级别下的幻读问题#xff0c;就引出了next-key 锁#xff0c;是记录锁和间隙锁的组合。 Record Lock#xff0c;记录锁#xff0c;锁的是记录本身…5.4 MySQL死锁了怎么办 RR隔离级别下会存在幻读的问题InnoDB为了解决RR隔离级别下的幻读问题就引出了next-key 锁是记录锁和间隙锁的组合。 Record Lock记录锁锁的是记录本身 Gap Lock间隙锁锁的就是两个值之间的空隙以防止其他事务在这个空隙间插入新的数据从而避免幻读现象。 我们可以执行 select * from performance_schema.data_locks\G; 语句 确定事务加了什么类型的锁。
为什么会产生死锁 通过举例体现死锁问题 建了一张订单表其中 id 字段为主键索引order_no 字段普通索引也就是非唯一索引二级索引 CREATE TABLE t_order (id int NOT NULL AUTO_INCREMENT,order_no int DEFAULT NULL,create_date datetime DEFAULT NULL,PRIMARY KEY (id),KEY index_order (order_no) USING BTREE ) ENGINEInnoDB ;

插入六条记录id 1-6 、order_on 1001-1006事务A执行给订单做幂等性校验目的是为了保证不会出现重复的订单。 SELECT id FROM t_order WHERE order_no 1007 for UPDATE;执行该语句事务A在二级索引加了X型next-key锁范围是(1006 ∞]。 事务B执行插入数据。 Insert into t_order (order_no, create_date) values (1008, now());Insert 语句在正常执行时是不会生成锁结构的它是靠聚簇索引记录自带的 trx_id 隐藏列来作为隐式锁来保护记录的。但此时记录之间加有间隙锁隐式锁会转换为显示锁。 如果已加间隙锁此时会生成一个插入意向锁然后锁的状态设置为等待状态现象就是Insert语句被阻塞。 因为插入意向锁与间隙锁是冲突的所以当其它事务持有该间隙的间隙锁时需要等待其它事务释放间隙锁之后才能获取到插入意向锁。 间隙锁与间隙锁之间是兼容的吗 间隙锁的意义只在于阻止区间被插入因此是可以共存的。一个事务获取的间隙锁不会阻止另一个事务获取同一个间隙范围的间隙锁共享和排他的间隙锁是没有区别的他们相互不冲突且功能相同即两个事务可以同时持有包含共同间隙的间隙锁。next-key lock 是包含间隙锁记录锁的如果一个事务获取了 X 型的 next-key lock那么另外一个事务再获取相同范围的 X 型的 next-key lock 时是会被阻塞的。但是对于这种范围为 (1006, ∞] 的 next-key lock两个事务是可以同时持有的不会冲突。因为 ∞ 并不是一个真实的记录自然就不需要考虑 X 型与 S 型关系。 插入意向锁是什么 插入意向锁是一种特殊的间隙锁但不同于间隙锁的是该锁只用于并发插入操作。如果说间隙锁锁住的是一个区间那么「插入意向锁」锁住的就是一个点。因而从这个角度来说插入意向锁确实是一种特殊的间隙锁。

Insert语句是怎么加行级锁的 隐式锁就是在 Insert 过程中不加锁只有在特殊情况下才会将隐式锁转换为显示锁。 如果记录之间加有间隙锁为了避免幻读此时是不能插入记录的插入意向锁会被设置为等待状态 如果 Insert 的记录和已有记录存在唯一键冲突此时也不能插入记录会对这条记录加上S型的锁 至于是记录锁还是 next-key 锁跟是「主键冲突」还是「唯一二级索引冲突」有关系。 如果主键冲突RR,RC级别给已存在的主键索引记录添加S型记录锁。如果唯一二级索引冲突RR,RC级别给已存在的二级索引记录添加S型next-key锁。
如何避免死锁 死锁的四个必要条件互斥、占有且等待、不可强占用、循环等待。只要系统发生死锁这些条件必然成立但是只要破坏任意一个条件就死锁就不会成立。 在数据库层面有两种策略通过「打破循环等待条件」来解除死锁状态 设置事务等待锁的超时时间。当一个事务的等待时间超过该值后就对这个事务进行回滚于是锁就释放了另一个事务就可以继续执行了。在 InnoDB 中参数 innodb_lock_wait_timeout 是用来设置超时时间的默认值时 50 秒。开启主动死锁检测。主动死锁检测在发现死锁后主动回滚死锁链条中的某一个事务让其他事务得以继续执行。将参数 innodb_deadlock_detect 设置为 on表示开启这个逻辑默认就开启。
5.5 字节面试 加了什么锁导致死锁的 创建一张学生表其中id为主键索引其他都是普通字段。 执行事务事务 A 和 事务 B 都在执行 insert 语句后都陷入了等待状态前提没有打开死锁检测也就是发生了死锁因为都在相互等待对方释放锁。 Time1阶段此时事务 A 在主键索引INDEX_NAME : PRIMARY上加的是间隙锁锁范围是(20, 30)。唯一索引等值查询查询id不在索引中退化成间隙锁Time2阶段此时事务B在主键索引上加的是也是间隙锁和事务A相同。Time3阶段事务 A 的状态为等待状态LOCK_STATUS: WAITING因为向事务 B 生成的间隙锁范围 (20, 30)中插入了一条记录所以事务 A 的插入操作生成了一个插入意向锁LOCK_MODE:INSERT_INTENTION。Time4阶段与Time3阶段相同。 本次案例中事务 A 和事务 B 在执行完后 update 语句后都持有范围为(20, 30的间隙锁而接下来的插入操作为了获取到插入意向锁都在等待对方事务的间隙锁释放于是就造成了循环等待满足了死锁的四个条件互斥、占有且等待、不可强占用、循环等待因此发生了死锁。 Redis过期删除与内存淘汰 Redis使用的过期删除策略是什么 Redis 是可以对 key 设置过期时间的因此需要有相应的机制将已过期的键值对删除而做这个工作的就是过期键值删除策略。 Redis的过期字典中保存了数据库中所有key的过期时间。当我们查询一个keyRedis会首先检查key是否存在与过期字典中。 如果不再正常获取键值。如果存在则会进行比较时间之后判断。 Redis 使用的过期删除策略是「惰性删除定期删除」这两种策略配和使用。 惰性删除策略的做法是不主动删除过期键每次从数据库访问 key 时都检测 key 是否过期如果过期则删除该 key。 优点此策略使用很少的系统资源对CPU最友好。缺点过期的key会一直占用系统资源对内存不友好。 定期删除策略的做法是每隔一段时间「随机」从数据库中取出一定数量的 key 进行检查并删除其中的过期key。 优点通过限制删除操作执行时长和频率可以减少对CPU的影响同时也能删除部分数据避免对内存的影响。缺点难以确定删除操作执行时长和频率。
Redis持久化时对过期键会如何处理 Redis持久化文件有两种格式RDBRedis Database和 AOFAppend Only File。 RDB分为两个阶段为生成阶段和加载阶段。 RDB 文件生成阶段从内存状态持久化成 RDB文件的时候会对 key 进行过期检查过期的键「不会」被保存到新的 RDB 文件中因此 Redis 中的过期键不会对生成新 RDB 文件产生任何影响。RDB 加载阶段RDB 加载阶段时要看服务器是主服务器还是从服务器分别对应以下两种情况 如果 Redis 是「主服务器」运行模式的话在载入 RDB 文件时程序会对文件中保存的键进行检查过期键「不会」被载入到数据库中。如果 Redis 是「从服务器」运行模式的话在载入 RDB 文件时不论键是否过期都会被载入到数据库中。但由于主从服务器在进行数据同步时从服务器的数据会被清空。所以一般来说过期键对载入 RDB 文件的从服务器也不会造成影响。 AOF 文件分为两个阶段为写入阶段和 AOF 重写阶段。 AOF 文件写入阶段当 Redis 以 AOF 模式持久化时如果数据库某个过期键还没被删除那么 AOF 文件会保留此过期键当此过期键被删除后Redis 会向 AOF 文件追加一条 DEL 命令来显式地删除该键值。AOF 重写阶段执行 AOF 重写时会对 Redis 中的键值对进行检查已过期的键不会被保存到重写后的 AOF 文件中因此不会对 AOF 重写造成任何影响。
Redis 主从模式中对过期键会如何处理 当 Redis 运行在主从模式下时从库不会进行过期扫描从库对过期的处理是被动的。也就是即使从库中的 key 过期了如果有客户端访问从库时依然可以得到 key 对应的值像未过期的键值对一样返回。 从库的过期键处理依靠主服务器控制主库在 key 到期时会在 AOF 文件里增加一条 del 指令同步到所有的从库从库通过执行这条 del 指令来删除过期的 key。 Redis内存淘汰策略 在 Redis 的运行内存达到了某个阀值就会触发内存淘汰机制这个阀值就是我们设置的最大运行内存此值在 Redis 的配置文件中可以找到配置项为 maxmemory。 Redis 内存淘汰策略共有八种这八种策略大体分为「不进行数据淘汰」和「进行数据淘汰」两类策略。 不进行数据淘汰的策略 noeviction不进行驱逐Redis3.0之后默认的内存淘汰策略 它表示当运行内存超过最大设置内存时不淘汰任何数据而是不再提供服务直接返回错误。 进行数据淘汰的策略 在设置了过期时间的数据中进行淘汰 volatile-random随机淘汰设置了过期时间的任意键值volatile-ttlTime-To-Live优先淘汰更早过期的键值。volatile-lruLeast recently used最近最少使用Redis3.0 之前默认的内存淘汰策略淘汰所有设置了过期时间的键值中优先淘汰最久未用的键值volatile-lfuLeast Frequently Used最近最不常用Redis 4.0 后新增的内存淘汰策略淘汰所有设置了过期时间的键值中优先淘汰最近最不常用的键值 在所有数据范围内进行淘汰 allkeys-random随机淘汰任意键值;allkeys-lru淘汰整个键值中最久未用的键值allkeys-lfuRedis 4.0 后新增的内存淘汰策略淘汰整个键值中最不常用的键值。
LRU 算法和 LFU 算法有什么区别 LRU最近最少使用算法根据时间淘汰LFU最近最不常用算法根据使用次数淘汰。 在 LRU 算法中Redis 对象头的 24 bits 的 lru 字段是用来记录 key 的访问时间戳因此在 LRU 模式下Redis可以根据对象头中的 lru 字段记录的值来比较最后一次 key 的访问时间长从而淘汰最久未被使用的 key。 在 LFU 算法中Redis对象头的 24 bits 的 lru 字段被分成两段来存储高 16bit 存储 ldt(Last Decrement Time)低 8bit 存储 logc(Logistic Counter)。 ldt 是用来记录 key 的访问时间戳logc 是用来记录 key 的访问频次它的值越小表示使用频率越低越容易淘汰每个新加入的 key 的logc 初始值为 5。logc 并不是单纯的访问次数而是访问频次访问频率因为 logc 会随时间推移而衰减的。 LRU全称是 Least Recently Used 翻译为最近最少使用会选择淘汰最近最少使用的数据。 传统 LRU 算法的实现是基于「链表」结构链表中的元素按照操作顺序从前往后排列最新操作的键会被移动到表头当需要内存淘汰时只需要删除链表尾部的元素即可因为链表尾部的元素就代表最久未被使用的元素。Redis 并没有使用这样的方式实现 LRU 算法因为传统的 LRU 算法存在两个问题 需要用链表管理所有的缓存数据这会带来额外的空间开销当有数据被访问时需要在链表上把该数据移动到头端如果有大量数据被访问就会带来很多链表移动操作会很耗时进而会降低 Redis 缓存性能。 Redis 实现的是一种近似 LRU 算法目的是为了更好的节约内存它的实现方式是在 Redis 的对象结构体中添加一个额外的字段用于记录此数据的最后一次访问时间。当 Redis 进行内存淘汰时会使用随机采样的方式来淘汰数据它是随机取 5 个值此值可配置然后淘汰最久没有使用的那个。Redis 实现的 LRU 算法的优点 不用为所有的数据维护一个大链表节省了空间占用不用在每次数据访问时都移动链表项提升了缓存的性能 但是 LRU 算法有一个问题无法解决缓存污染问题比如应用一次读取了大量的数据而这些数据只会被读取这一次那么这些数据会留存在 Redis 缓存中很长一段时间造成缓存污染。引入LFU算法解决了这个问题。 LFU 全称是 Least Frequently Used 翻译为最近最不常用LFU 算法是根据数据访问次数来淘汰数据的。 Redis 在访问 key 时对于 logc 是这样变化的 先按照上次访问距离当前的时长来对 logc 进行衰减然后再按照一定概率增加 logc 的值。
Redis缓存设计 如何避免缓存雪崩、缓存击穿、缓存穿透 缓存的作用 通常我们为了保证缓存中的数据与数据库中的数据一致性会给 Redis 里的数据设置过期时间当缓存数据过期后用户访问的数据如果不在缓存里业务系统需要重新生成缓存因此就会访问数据库并将数据更新到 Redis 里这样后续请求都可以直接命中缓存。 缓存雪崩 大量缓存数据在同一时间过期失效时如果此时有大量的用户请求都无法在 Redis 中处理于是全部请求都直接访问数据库从而导致数据库的压力骤增严重的会造成数据库宕机从而形成一系列连锁反应造成整个系统崩溃这就是缓存雪崩的问题。 对于缓存雪崩可以采用两种方案解决 将缓存失效时间随机打散 我们可以在原有的失效时间基础上增加一个随机值比如 1 到 10 分钟这样每个缓存的过期时间都不重复了也就降低了缓存集体失效的概率。设置缓存不过期 我们可以通过后台服务来更新缓存数据从而避免因为缓存失效造成的缓存雪崩也可以在一定程度上避免缓存并发问题。 缓存击穿 如果缓存中的某个热点数据过期了此时大量的请求访问了该热点数据就无法从缓存中读取直接访问数据库数据库很容易就被高并发的请求冲垮这就是缓存击穿的问题。可以认为缓存击穿是缓存雪崩的一个子集。 对于缓存击穿可以采取两种方案 互斥锁方案Redis 中使用 setNX 方法设置一个状态位表示这是一种锁定状态保证同一时间只有一个业务线程请求缓存将所有的访问变成互斥操作未能获取互斥锁的请求要么等待锁释放后重新读取缓存要么就返回空值或者默认值。 不给热点数据设置过期时间由后台异步更新缓存或者在热点数据准备要过期前提前通知后台线程更新缓存以及重新设置过期时间 缓存穿透 当用户访问的数据既不在缓存中也不在数据库中导致请求在访问缓存时发现缓存缺失再去访问数据库时发现数据库中也没有要访问的数据没办法构建缓存数据来服务后续的请求。那么当有大量这样的请求到来时数据库的压力骤增这就是缓存穿透的问题。 缓存穿透的发生一般有这两种情况业务误操作黑客恶意攻击。缓存穿透的方案常见的方案有三种。 非法请求的限制当有大量恶意请求访问不存在的数据的时候也会发生缓存穿透因此在 API 入口处我们要判断求请求参数是否合理请求参数是否含有非法值、请求字段是否存在如果判断出是恶意请求就直接返回错误避免进一步访问缓存和数据库。设置空值或者默认值当我们线上业务发现缓存穿透的现象时可以针对查询的数据在缓存中设置一个空值或者默认值这样后续请求就可以从缓存中读取到空值或者默认值返回给应用而不会继续查询数据库。使用布隆过滤器快速判断数据是否存在避免通过查询数据库来判断数据是否存在我们可以在写入数据库数据时使用布隆过滤器做个标记然后在用户请求到来时业务线程确认缓存失效后可以通过查询布隆过滤器快速判断数据是否存在如果不存在就不用通过查询数据库来判断数据是否存在即使发生了缓存穿透大量请求只会查询 Redis 和布隆过滤器而不会查询数据库保证了数据库能正常运行Redis 自身也是支持布隆过滤器的。 布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多。
如何设计一个缓存策略可以动态缓存热点数据呢 由于数据存储受限系统并不是将所有数据都需要存放到缓存中的而只是将其中一部分热点数据缓存起来所以我们要设计一个热点数据动态缓存的策略。 热点数据动态缓存的策略总体思路通过数据最新访问时间来做排名并过滤掉不常访问的数据只留下经常访问的数据。 以电商平台场景中的例子现在要求只缓存用户经常访问的 Top 1000 的商品。具体细节如下 先通过缓存系统做一个排序队列比如存放 1000 个商品系统会根据商品的访问时间更新队列信息越是最近访问的商品排名越靠前同时系统会定期过滤掉队列中排名最后的 200 个商品然后再从数据库中随机读取出 200 个商品加入队列中这样当请求每次到达的时候会先从队列中获取商品 ID如果命中就根据 ID 再从另一个缓存数据结构中读取实际的商品信息并返回。 在 Redis 中可以用 zadd 方法和 zrange 方法来完成排序队列和获取 200 个商品的操作。 说说常见的缓存更新策略 常见的缓存更新策略共有3种 Cache Aside旁路缓存策略最常用应用程序直接与「数据库、缓存」交互并负责对缓存的维护该策略又可以细分为「读策略」和「写策略」。 写策略先更新数据库中的数据再删除缓存中的数据。 不能颠倒会出现缓存和数据库不一致的问题。不颠倒因为缓存的写入通常要远远快于数据库的写入所以在实际中很难出现 写策略A已经更新了数据库并且删除了缓存读策略B才更新完缓存的情况。而一旦请求 A 早于请求 B 删除缓存之前更新了缓存那么接下来的请求就会因为缓存不命中而从数据库中重新读取数据所以不会出现这种不一致的情况。 读策略如果读取的数据命中了缓存则直接返回数据否则从数据库中读取数据然后将数据写入到缓存并且返回给用户。Cache Aside 策略适合读多写少的场景不适合写多的场景因为当写入比较频繁时缓存中的数据会被频繁地清理这样会对缓存的命中率有一些影响。如果业务对缓存命中率有严格的要求那么可以考虑两种解决方案 一种做法是在更新数据时也更新缓存只是在更新缓存前先加一个分布式锁同一时间只允许一个线程更新缓存就不会产生并发问题。当然这么做对于写入的性能会有一些影响另一种做法同样也是在更新数据时更新缓存只是给缓存加一个较短的过期时间这样即使出现缓存不一致的情况缓存的数据也会很快过期对业务的影响也是可以接受。 Read/Write Through读穿 / 写穿策略该策略原则是应用程序只和缓存交互不再和数据库交互而是由缓存和数据库交互相当于更新数据库的操作由缓存自己代理了。 1、Read Through 策略 先查询缓存中数据是否存在如果存在则直接返回如果不存在则由缓存组件负责从数据库查询数据并将结果写入到缓存组件最后缓存组件将数据返回给应用。 2、Write Through 策略 当有数据更新的时候先查询要写入的数据在缓存中是否已经存在 如果缓存中数据已经存在则更新缓存中的数据并且由缓存组件同步更新到数据库中然后缓存组件告知应用程序更新完成。如果缓存中数据不存在直接更新数据库然后返回 我们经常使用的分布式缓存组件无论是 Memcached 还是 Redis 都不提供写入数据库和自动加载数据库中的数据的功能所以不常用。 Write Back写回策略在更新数据的时候只更新缓存同时将缓存数据设置为脏的然后立马返回并不会更新数据库。对于数据库的更新会通过批量异步更新的方式进行。缺点是数据不是强一致性的而且会有数据丢失的风险 Write Back写回策略也不能应用到我们常用的数据库和缓存的场景中因为 Redis 并没有异步更新数据库的功能。 583. 两个字符串的删除操作 - 力扣LeetCode dp[i][j]以i - 1结尾的word1和以j - 1结尾的word2删除字符后使两个单词相等的最小删除步数为dp[i][j]。 word1[i - 1] word2[j - 1]不需要删除dp[i][j] dp[i - 1][j - 1]。 word1[i - 1] ! word2[j - 1]需要删除删除word1或删除word2dp[i][j] Math.min(dp[i - 1][j] 1, dp[i][j - 1] 1) dp[i][0]word2为空字符串以i-1为结尾的字符串word1要删除多少个元素才能和word2相同呢很明显dp[i][0] i。dp[0][j]的话同理。 遍历顺序从前往后从上往下遍历。 举例推导dp class Solution {public int minDistance(String word1, String word2) {int m word1.length();int n word2.length();int [] [] dp new int [m 1][n 1];for(int i 0 ; i m ; i ){dp[i][0] i;}for(int j 0 ; j n ; j ){dp[0][j] j;}for(int i 1 ; i m ; i ){char w1 word1.charAt(i - 1);for(int j 1 ; j n ; j ){char w2 word2.charAt(j - 1);if(w1 w2) dp[i][j] dp[i - 1][j - 1];else dp[i][j] Math.min(dp[i - 1][j] 1 , dp[i][j - 1] 1);//System.out.println(以word1[ (i - 1) ]和word[ (j - 1) ]结尾的单词最少需要 dp[i][j] 步删除才能使word1与word2相等);}}return dp[m][n];} }72. 编辑距离 - 力扣LeetCode dp[i][j]以i - 1结尾的word1和以j - 1结尾的word2转换所需的最小操作数为dp[i][j]。 word1[i] word2[j] 不需要进行操作dp[i][j] dp[i - 1][j - 1]。 word1[i - 1] ! word2[j - 1]需要进行操作 删除添加word2删除一个元素相当于word1添加一个元素。 word1删除一个元素dp[i][j] dp[i - 1][j] 1。 word2删除一个元素word1添加元素dp[i][j] dp[i][j - 1] 1 替换可以回顾一下if (word1[i - 1] word2[j - 1])的时候我们的操作 是 dp[i][j] dp[i - 1][j - 1] 对吧。 那么只需要一次替换的操作就可以让 word1[i - 1] 和 word2[j - 1] 相同。所以 dp[i][j] dp[i - 1][j - 1] 1; dp数组初始化dp[i][0] 以下标i-1为结尾的字符串word1和空字符串word2最近编辑距离为dp[i][0]。 那么dp[i][0]就应该是i对word1里的元素全部做删除操作即dp[i][0] i; 同理dp[0][j] j; 从上往下从左往右遍历。 举例推导dp数组 class Solution {public int minDistance(String word1, String word2) {int m word1.length();int n word2.length();int [] [] dp new int [m 1][n 1];for(int i 0 ; i m ; i ){dp[i][0] i;}for(int j 0 ; j n ; j ){dp[0][j] j;}for(int i 1 ; i m ; i ){char w1 word1.charAt(i - 1);for(int j 1 ; j n ; j ){char w2 word2.charAt(j - 1);if(w1 w2) dp[i][j] dp[i - 1][j - 1];else dp[i][j] Math.min(dp[i - 1][j - 1] 1 , Math.min(dp[i - 1][j] 1 , dp[i][j - 1] 1));//System.out.println(以word1[ (i - 1) ]和word2[ (j - 1) ]结尾的单词word1最少需要 dp[i][j] 步操作才能使word1与word2相等);}}return dp[m][n];} }回文串问题 题目关键点647. 回文子串 - 力扣LeetCodedp数组定义516. 最长回文子序列 - 力扣LeetCodedp数组定义647. 回文子串 - 力扣LeetCode 判断一个子字符串字符串的下表范围[i,j]是否回文依赖于子字符串下表范围[i 1, j - 1] 是否是回文。 所以定义一个boolean类型的dp[i][j]表示区间范围[i , j ]的子串是否回文。 s[i] s[j]时分三种情况 下标i ja dp[i][j] true 下标i与j相差为1aadp[i][j] true 下标i与j相差大于1cabac此时就看dp[i 1][j - 1]是不是回文即可。 dp[i][j]初始化为false。正好也解决了当s[i] ! s[j]时的问题。 遍历顺序 dp[i 1][j - 1] 在 dp[i][j]的左下角如图 所以应该从下往上从左到右遍历。 举例推导dp数组 class Solution {public int countSubstrings(String s) {//记录回文串数量。int ans 0;int m s.length();boolean dp [][] new boolean [m][m];for(int i m - 1; i 0 ; i –){char si s.charAt(i);for(int j i ; j m ; j ){char sj s.charAt(j);if(si sj){if( j - i 1){ans ;dp[i][j] true;}else if(dp[i 1][j - 1]){ans ;dp[i][j] true;}}// System.out.println(以[ i , j ]为区间的字符串 dp[i][j]回文串);}}return ans;} }516. 最长回文子序列 - 力扣LeetCode dp数组初始化dp[i][j]字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。 递推公式如果s[i] s[j] 那么dp[i][j] dp[i 1][j - 1] 2。 如果s[i] ! s[j] 那么就是根据加上s[i]或者加上s[j]两种情况的不同长度来判断dp[i][j] Math.max(dp[i 1][j] , dp[i][j - 1])。 初始化dp[i][j] dp[i 1][j - 1] 2计算不到相同的情况所以当i j时初始化为1。 遍历顺序与上一题一致 举例推导dp数组 class Solution {public int longestPalindromeSubseq(String s) {int m s.length();int [][] dp new int [m][m];for(int i 0 ; i m ; i ){dp[i][i] 1;}for(int i m - 1 ; i 0 ; i –){char si s.charAt(i);for(int j i 1; j m ; j ){char sj s.charAt(j);if(si sj){dp[i][j] dp[i 1][j - 1] 2;}else {dp[i][j] Math.max(dp[i 1][j] , dp[i][j - 1]);}}}return dp[0][m - 1];} }