【蓝桥杯】动态规划：线性动态规划

1. 最长上升子序列（LIS）

1.1. 题目

想象你有一排数字，比如：3, 1, 2, 1, 8, 5, 6

你要从中挑出一些数字，这些数字要满足两个条件：

1. 你挑的数字的顺序要和原来序列中的顺序一致（不能打乱顺序）

2. 你挑的数字要一个比一个大（严格递增）

问：最多能挑出多少个这样的数字？

比如上面这个例子：

• 可以挑 3, 8（但长度只有2）

• 可以挑 1, 2, 5, 6（长度是4）

• 也可以挑 1, 2, 8（长度是3）

最长的就是4，所以答案是4

1.2. 思路（动态规划）

我们用一个数组dp来记录：

• dp[i] 表示：以第i个数字结尾时，能组成的最长上升子序列的长度

比如对于序列 [3,1,2,1,8,5,6]：

1. 第一个数字3：只能选它自己，所以dp[0]=1

2. 第二个数字1：比3小，不能接在3后面，只能自己开头，dp[1]=1

3. 第三个数字2：

   • 可以接在1后面（1<2），所以长度=dp[1]+1=2

   • 不能接在3后面（3>2）

   • 所以dp[2]=2

4. 第四个数字1：

   • 比前面的3,1,2都小，只能自己开头

   • dp[3]=1

5. 第五个数字8：

   • 可以接在3后面（3<8），长度=dp[0]+1=2

   • 可以接在1后面（1<8），长度=dp[1]+1=2

   • 可以接在2后面（2<8），长度=dp[2]+1=3

   • 可以接在前面的1后面（1<8），长度=dp[3]+1=2

   • 最大的是3，所以dp[4]=3

6. 继续计算最后两个数字...最终dp = [1,1,2,1,3,3,4]

7. 最大值是4，所以答案是4

1.3. 完整代码（动态规划）

n = int(input())  # 先读取数字的个数
nums = list(map(int, input().split()))  # 读取数字序列# 初始化dp数组，每个数字自己就是一个长度为1的子序列
dp = [1] * n  # 从第二个数字开始检查（因为第一个数字的dp值肯定是1）
for i in range(1, n):# 看看前面所有数字for j in range(i):# 如果前面的数字比当前数字小，就可以接在后面if nums[j] < nums[i]:# 更新dp[i]，选择更大的值dp[i] = max(dp[i], dp[j] + 1)# 相当于说："如果接在这个数字后面，会不会让序列更长&#