【算法】动态规划专题② ——LIS（最长递增子序列） python

前置知识

【算法】动态规划专题① ——线性DP python

问题描述

题目是说：
给定一个整数数组，找到其中最长的严格递增子序列的长度。（子序列不要求连续）

比如说，像数组 [10,9,2,5,3,7,101,18]，最长递增子序列是 [2,5,7,101]，所以长度是4。

那要怎么做呢？

DP解法

对于每个元素，遍历它前面的所有元素，如果前面的元素比它小，那么就可以在这个元素的基础上形成更长的子序列。
再维护一个dp数组，其中dp[ $i$ ]表示以第 $i$ 个元素结尾的最长子序列的长度

那具体步骤是怎么样的呢？

初始化dp[ $i$ ]=1，然后，
对于每个 $i$ ，从 $j$ =0到 $i$ -1遍历，
如果nums[ $i$ ] > nums[ $j$ ]，那么dp[ $i$ ] = max(dp[ $i$ ], dp[ $j$ ] + 1)。
这样处理完所有元素之后，最大的dp值就是结果。

比如上面的例子，数组是[10,9,2,5,3,7,101,18]，对应的dp数组应该怎么算？

初始dp都是1。第一个元素10，前面没有元素，dp[0]=1。第二个元素9，比10小，所以不能接在后面，所以dp[1]=1。第三个元素2，同样比前面两个都小，所以dp[2]=1。第四个元素5，前面有元素2，所以dp[3] = dp[2]+1=2。接下来第五个元素3，比它前面的一些元素大吗？比如，3比2大，所以dp[4] = dp[2]+1=2。第六个元素7，前面比它小的有2、5、3，所以这时候要看这些位置上的dp值加1的最大值。比如，2对应的dp是1，5对应的dp是2，3对应的dp是2。所以最大的加1是3，所以dp[5]=3。第七个元素101，前面所有比它小的元素对应的dp值的最大值是3，所以dp[6]=4。最后一个元素18，前面比它小的元素中最大的dp值可能是3（比如7的位置），所以dp[7] =4。那么最大的dp是4，即答案为4。

示例：

python">a = [10, 9, 2, 5, 3, 7, 101, 18]
n = len(a)
dp = [0] * n
for i in range(n):dp[i] = 1  # 单独一个元素本身就是一个长度为1的子序列for j in range(i):if a[j] < a[i]:dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))  # 4（2，3，7，101）

小试牛刀

蓝桥勇士 https://www.lanqiao.cn/problems/2049/learning/?page=1&first_category_id=1&problem_id=2049

题目描述

小明是蓝桥王国的勇士，他晋升为蓝桥骑士，于是他决定不断突破自我。
这天蓝桥首席骑士长给他安排了N个对手，他们的战力值分别为a1,a2,an,且按顺序阻挡在小明的前方。对于这些对手小明可以选择挑战，也可以选择避战。
作为热血豪放的勇士，小明从不走回头路，且只愿意挑战战力值越来越高的对手。
请你算算小明最多会挑战多少名对手。

输入描述：
输入第一行包含一个整数N,表示对手的个数。
第二行包含N个整数a1,a2,······,an,分别表示对手的战力值。
1≤N≤1e3,1≤a≤1e9。

输出描述：
输出一行整数表示答案。

示例输入：

6
1 4 3 2 5 6

示例输出：

code实现：

python">n = int(input())
a = list(map(int, input().split()))
dp = [0] * n
for i in range(n):dp[i] = 1 for j in range(i):if a[j] < a[i]:dp[i] = max(dp[i], dp[j] + 1)
ans = max(dp)
print(ans)

举一反三

既然有最长递增子序列，那是不是也得有最长下降子序列
这又该怎么求呢？

类似地：

python">a = [10, 9, 2, 5, 3, 7, 101, 18]
n = len(a)
dp = [0] * n
for i in range(n - 1, -1, -1):dp[i] = 1for j in range(i + 1, n):if a[i] > a[j]:dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))  # 4（10，9，5，3）

好了，实际运用的时候到了

实战演练

合唱队形 https://www.lanqiao.cn/problems/742/learning/?page=1&first_category_id=1&problem_id=742

题目描述

N位同学站成一排，音乐老师要请其中的(N一K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,······K,他们的身高分别为T1,T2,······,TK,则他们的身高满足
T1<···Ti+1>···>Tk(1≤i≤K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入描述

输入两行
第一行是一个整数N(2≤N≤100)，表示同学的总数。
第二行有n个整数，用空格分隔，第i个整数Ti(130≤T≤230)是第i位同学的身高（厘米）。

输出描述

输出一个整数，就是最少需要几位同学出列。

示例输入：

8
186 186 150 200 160 130 197 220

示例输出：

思路分析：

求出最长递增子序列和最长下降子序列相加的最大值 -1 即可

题解code：

python">n = int(input())
a = list(map(int, input().split()))dp1 = [0] * n
dp2 = [0] * n
for i in range(n):dp1[i] = 1for j in range(i):if a[i] > a[j]:dp1[i] = max(dp1[i], dp1[j] + 1)for i in range(n - 1, -1, -1):dp2[i] = 1for j in range(i + 1, n):if a[i] > a[j]:dp2[i] = max(dp2[i], dp2[j] + 1)res = max(dp1[x] + dp2[x] - 1 for x in range(n))
print(n - res)

总结

动态规划解法以清晰的逻辑展现 LIS （最长递增子序列）问题的递推本质，是算法学习的经典案例。
当然，此解法时间复杂度是O(n^2)，当n较大时，比如1e4或1e5，会超时。
那有没有更优的解法？比如O(n log n)的解法？
答案是有的。二分 + 贪心 的做法，
不过在此就不多赘述了，感兴趣的可以自己思考一下。

END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！
如果喜欢的话，请给博主点个关注谢谢