【3.1】MySQL锁、动态规划、Redis缓存，过期删除与淘汰策略

5.4 MySQL死锁了，怎么办？

• RR隔离级别下，会存在幻读的问题，InnoDB为了解决RR隔离级别下的幻读问题，就引出了next-key 锁，是记录锁和间隙锁的组合。

  • Record Lock，记录锁，锁的是记录本身；

  • Gap Lock，间隙锁，锁的就是两个值之间的空隙，以防止其他事务在这个空隙间插入新的数据，从而避免幻读现象。

• 我们可以执行 select * from performance_schema.data_locks\G; 语句 ，确定事务加了什么类型的锁。

为什么会产生死锁？

• 通过举例体现死锁问题：

  0. 建了一张订单表，其中 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
     ) ENGINE=InnoDB ;
     # 插入六条记录，id 1-6 、order_on 1001-1006
     

  1. 事务A执行：给订单做幂等性校验，目的是为了保证不会出现重复的订单。

     SELECT id FROM t_order WHERE `order_no` = 1007 for UPDATE;
     

     执行该语句，事务A在二级索引加了X型next-key锁，范围是(1006 ， +∞]。

  2. 事务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的过期时间。当我们查询一个key，Redis会首先检查key是否存在与过期字典中。
  • 如果不再，正常获取键值。
  • 如果存在，则会进行比较时间之后判断。
• Redis 使用的过期删除策略是「惰性删除+定期删除」这两种策略配和使用。
  • 惰性删除策略的做法是，不主动删除过期键，每次从数据库访问 key 时，都检测 key 是否过期，如果过期则删除该 key。
    • 优点：此策略使用很少的系统资源，对CPU最友好。缺点：过期的key会一直占用系统资源，对内存不友好。
  • 定期删除策略的做法是，每隔一段时间「随机」从数据库中取出一定数量的 key 进行检查，并删除其中的过期key。
    • 优点：通过限制删除操作执行时长和频率，可以减少对CPU的影响，同时也能删除部分数据，避免对内存的影响。缺点：难以确定删除操作执行时长和频率。

Redis持久化时，对过期键会如何处理？

Redis持久化文件有两种格式：RDB（Redis Database）和 AOF（Append 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 内存淘汰策略共有八种，这八种策略大体分为「不进行数据淘汰」和「进行数据淘汰」两类策略。

1. 不进行数据淘汰的策略
   • noeviction（不进行驱逐）（Redis3.0之后，默认的内存淘汰策略） ：它表示当运行内存超过最大设置内存时，不淘汰任何数据，而是不再提供服务，直接返回错误。
2. 进行数据淘汰的策略
   • 在设置了过期时间的数据中进行淘汰：
     • volatile-random：随机淘汰设置了过期时间的任意键值；
     • volatile-ttl（Time-To-Live）：优先淘汰更早过期的键值。
     • volatile-lru（Least recently used，最近最少使用）（Redis3.0 之前，默认的内存淘汰策略）：淘汰所有设置了过期时间的键值中，优先淘汰最久未用的键值；
     • volatile-lfu（Least Frequently Used，最近最不常用）（Redis 4.0 后新增的内存淘汰策略）：淘汰所有设置了过期时间的键值中，优先淘汰最近最不常用的键值；
   • 在所有数据范围内进行淘汰：
     • allkeys-random：随机淘汰任意键值;
     • allkeys-lru：淘汰整个键值中最久未用的键值；
     • allkeys-lfu（Redis 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 是这样变化的：
    1. 先按照上次访问距离当前的时长，来对 logc 进行衰减；
    2. 然后，再按照一定概率增加 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）

  1. dp[i][j]：以i - 1结尾的word1和以j - 1结尾的word2，删除字符后使两个单词相等的最小删除步数为dp[i][j]。

  2. 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)

  3. dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。dp[0][j]的话同理。

  4. 遍历顺序从前往后，从上往下遍历。

  5. 举例推导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）

  1. dp[i][j]：以i - 1结尾的word1和以j - 1结尾的word2，转换所需的最小操作数为dp[i][j]。

  2. 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;

  3. dp数组初始化：dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。

     那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;

     同理dp[0][j] = j;

  4. 从上往下，从左往右遍历。

  5. 举例推导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. 回文子串 - 力扣（LeetCode）	dp数组定义
516. 最长回文子序列 - 力扣（LeetCode）	dp数组定义

• 647. 回文子串 - 力扣（LeetCode）

  判断一个子字符串（字符串的下表范围[i,j]）是否回文，依赖于，子字符串（下表范围[i + 1, j - 1]）） 是否是回文。

  1. 所以定义一个boolean类型的dp[i][j]，表示区间范围[i , j ]的子串是否回文。

  2. s[i] == s[j]时分三种情况：

     下标i == j（a）： dp[i][j] = true

     下标i与j相差为1（aa）：dp[i][j] = true

     下标i与j相差大于1（cabac）：此时就看dp[i + 1][j - 1]是不是回文即可。

  3. dp[i][j]初始化为false。正好也解决了当s[i] != s[j]时的问题。

  4. 遍历顺序：

     dp[i + 1][j - 1] 在 dp[i][j]的左下角，如图：

     所以应该从下往上，从左到右遍历。

  5. 举例推导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）

  1. dp数组初始化：dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

  2. 递推公式：如果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])。

  3. 初始化：dp[i][j] = dp[i + 1][j - 1] + 2计算不到相同的情况，所以当i == j时，初始化为1。

  4. 遍历顺序与上一题一致

  5. 举例推导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];}
     }