线性dp
线性dp主要是一些子序列问题和数字三角形问题,思考的方式还是从状态表示和状态转移两个方面
最长上升子序列
题目描述:给你一个整数数组 nums
,找到其中最长严格递增子序列的长度。
这里的子数组是指删除数组中的元素而不改变其元素的顺序不一定是要连续的。例如,[3,6,2,7]
是数组 [0,3,1,6,2,2,7]
的子序列。
动态规划问题还是从状态表示和状态转移两个方面来思考。对于一个序列问题来说,状态表示一般是一维的,dp(i)表示以第i个数字结尾递增子序列的集合,属性是max,最长的。现在考虑状态转移方程,还是从集合划分的角度来思考。考虑第i-1个数,可能的情况,那其实就有i-1种,全部枚举,求max就好了。当然得先判断第i-1个数是小于第i个数的。最后再枚举一下以各个数结尾最长子序列的长度,求最大就可以了。
代码如下
1 | class Solution { |
这个题还有一个以贪心为思路的优化方法。这里就不写了,有点难想。。
最长公共子序列
这道题是求两个字符串最长公共子序列的长度。子序列的定义和上面的题一样,只要相对顺序与原字符串保持一致即可。
还是从状态表示和状态转移方程来考虑。这里有两个字符串,那么dp状态应该就是二维的。用dp(i,j)表示第一个字符串的前i个和第二个字符串的前j个 公共子序列的最大值。状态转移还是从集合划分来考虑。考虑选或者不选第i,j个的情况。那么就有4种 dp(i-1,j-1),dp(i-1,j),dp(i,j-1), dp(i-1,j-1)+1。第一个和最后一个是不选i,j和选i,j的情况。注意一下,中间两种并不是没选i、选j,和选了i,没选j的情况。因为dp(i-1,j)并不表示一定选了j,所以前面三种情况的集合是互相有包含的,但是涵盖了所有的情况,所以我们只需要取max就行了。
代码如下:
1 | class Solution { |
编辑距离
Leetcode72编辑距离是一道很经典的问题,也是两个字符串的问题。题意是 给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。操作包括,删除字符,插入字符和替换字符。比如word1 = “horse”, word2 = “ros” ,要变成相同的两个字符串的话可以将h替换为r–>’rorse’ 再将第三个r删除–>’rose’,最后再将最后的e删除就可以了。这样的话距离就是3.
两个字符串的状态表示可以这么考虑,dp(i,j)表示将word1前i个字符变成word2前j个字符的操作方式。那么属性就是最小值。然后还是从集合划分的角度来考虑。我们对word1的操作有四种情况,增删改,还有一种是什么都不做,在word1(i)和word2(j)相等的情况下。删除的话就是dp(i,j)=dp(i-1,j)+1,增加的话dp(i,j-1)+1,替换的话就是直接将最后一个字母替换成word2的第j个dp(i-1,j-1)+1。那么什么时候该用哪一种呢,个不需要考虑,由于求的是最小值,所以我们将上述四种情况去min就好了。确定一下base case。就是两个字符串有一个为空的情况,那么直接返回另一个字符串的长度就好了。
代码如下
1 | class Solution { |
还有一个很经典的问题,最大子序和,这个问题可以用dp的方法思考,但不是最优解,最优解法是贪心的思路,所以就放在贪心的笔记里。
可以看到子序列问题中,有两类,一个是一个子序列,如最长上升子序列,还有的是两个子序列。那么有两种状态表示方式。一维的:以a(i)为结尾的目标子序列。二维的:dp(i,j)表示第一个字符串的前i个和第二个字符串的前j个…可以这样来思考子序列的最值问题。