×

由于本站访问压力较大
微信扫码关注公众号 labuladong
回复关键词「解锁
按照操作即可解锁本站全部文章

公众号

动态规划之子序列问题解题模板

通知: 数据结构精品课 已更新到 V2.0,2022 年最后一期打卡训练营 最后一天报名

读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:

LeetCode 力扣 难度
1312. Minimum Insertion Steps to Make a String Palindrome 1312. 让字符串成为回文串的最少插入次数 🔴
516. Longest Palindromic Subsequence 516. 最长回文子序列 🟠

———–

子序列问题是常见的算法问题,而且并不好解决。

首先,子序列问题本身就相对子串、子数组更困难一些,因为前者是不连续的序列,而后两者是连续的,就算穷举你都不一定会,更别说求解相关的算法问题了。

而且,子序列问题很可能涉及到两个字符串,比如前文 最长公共子序列,如果没有一定的处理经验,真的不容易想出来。所以本文就来扒一扒子序列问题的套路,其实就有两种模板,相关问题只要往这两种思路上想,十拿九稳。

一般来说,这类问题都是让你求一个最长子序列,因为最短子序列就是一个字符嘛,没啥可问的。一旦涉及到子序列和最值,那几乎可以肯定,考察的是动态规划技巧,时间复杂度一般都是 O(n^2)

原因很简单,你想想一个字符串,它的子序列有多少种可能?起码是指数级的吧,这种情况下,不用动态规划技巧,还想怎么着?

既然要用动态规划,那就要定义 dp 数组,找状态转移关系。我们说的两种思路模板,就是 dp 数组的定义思路。不同的问题可能需要不同的 dp 数组定义来解决。

一、两种思路

_____________

应合作方要求,本文不便在此发布,请扫码关注回复关键词「子序列」或 点这里 查看:

共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释