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

GitHub undefined undefined undefined

培养框架思维,真正爱上算法!关注公众号查看更新文章👆

相关推荐:

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

516.最长回文子序列(中等)


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

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

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

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

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

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

一、两种思路

_____________

本文只能在 labuladong 公众号查看,关注后可直接搜索本站内容:

Copyright © labuladong 2020 all right reserved,powered by Gitbook该文件修订时间: 2021-04-19 18:19:24

results matching ""

    No results matching ""