一、写在前面兄弟们Day 27今天一口气刷了五道动态规划的经典模型题每一道都是蓝桥杯考场上必考必会的题型。从最基础的LIS到多重背包从数字三角形到最长公共子序列这些模板如果能在考场上直接默写出来至少能省下20分钟。今天的五道题最长上升子序列(LIS) —— 线性DP入门合唱队形 —— LIS正序逆序最长公共子序列(LCS) —— 二维DP经典数字三角形 —— 递推DP摆花 —— 多重背包二、第一题最长上升子序列难度⭐⭐⭐2.1 题目大意给定一个长度为 n 的序列求最长的严格上升子序列的长度。2.2 解题思路这是最经典的动态规划模型之一。状态定义dp[i]表示以第 i 个数字结尾的最长上升子序列的长度。状态转移对于每个 i枚举前面的所有 jj i如果a[j] a[i]说明 a[i] 可以接在 a[j] 后面更新dp[i] max(dp[i], dp[j] 1)。最终答案max(dp)因为最长上升子序列的结尾不一定在哪个位置。2.3 代码实现nint(input())a[0]list(map(int,input().split()))# 下标从1开始dp[0]*(n1)foriinrange(1,n1):# 至少包含自己长度为1dp[i]1# 在i的前面找小于a[i]的数字forjinrange(1,i):ifa[j]a[i]:dp[i]max(dp[i],dp[j]1)print(max(dp))2.4 时间复杂度分析时间复杂度O(n²)双重循环空间复杂度O(n)对于 n ≤ 10⁵ 的数据会超时需要用到二分优化 patience sorting 算法时间复杂度降到 O(n log n)。但蓝桥杯大部分题目 n ≤ 1000O(n²) 完全够用。2.5 踩坑记录下标从1开始a [0] list(...)这样 a[1] 就是第一个元素方便处理初始状态dp[i] 1每个元素至少可以单独成一个子序列最终答案取max(dp)不是dp[n]严格上升条件是不是三、第二题合唱队形难度⭐⭐⭐⭐3.1 题目大意N 位同学站成一排音乐老师要请其中的 N-K 位同学出列使得剩下的 K 位同学排成合唱队形。合唱队形是指设 K 位同学从左到右依次编号为 1,2,…,K他们的身高分别为 T1,T2,…,TK则 T1 T2 … Ti且 Ti Ti1 … TK1 ≤ i ≤ K。也就是说合唱队形是一个先严格上升再严格下降的序列。求最少需要出列多少位同学。3.2 解题思路这道题是LIS的变形。对于每个位置 i我们需要知道dp1[i]以 i 结尾的最长上升子序列长度从左往右dp2[i]从 i 开始的最长下降子序列长度从右往左然后枚举每个位置 i 作为最高点以 i 为最高点的合唱队形长度 dp1[i] dp2[i] - 1i 被算了两次减1。最终答案n - max(dp1[i] dp2[i] - 1)3.3 代码实现nint(input())a[0]list(map(int,input().split()))# dp1[i]以i结尾的最长上升子序列长度正序dp1[0][1]*nforiinrange(1,n1):forjinrange(1,i):ifa[j]a[i]:dp1[i]max(dp1[i],dp1[j]1)# dp2[i]从i开始的最长下降子序列长度逆序dp2[0][1]*nforiinrange(n,0,-1):forjinrange(i1,n1):ifa[i]a[j]:# 注意这里是下降所以是 dp2[i]max(dp2[i],dp2[j]1)# 枚举最高点求最大合唱队形长度ansmax([dp1[i]dp2[i]-1foriinrange(1,n1)])print(n-ans)3.4 关键技巧正序LIS从左往右递推找前面比当前小的逆序LDS从右往左递推找后面比当前小的等价于从右往左的LIS合并时减1最高点被两个DP数组各算了一次要去重3.5 踩坑记录dp2的递推方向从右往左range(n, 0, -1)dp2的比较条件a[i] a[j]因为要找下降的最终答案n - ans不是ans题目问的是最少出列多少人列表推导式[dp1[i] dp2[i] - 1 for i in range(1, n 1)]简洁高效四、第三题最长公共子序列难度⭐⭐⭐⭐4.1 题目大意给定两个序列 A 和 B求它们的最长公共子序列LCS的长度。如果需要还要输出这个子序列。4.2 解题思路二维DP的经典模型。状态定义dp[i][j]表示 A 的前 i 个元素和 B 的前 j 个元素的最长公共子序列长度。状态转移如果a[i] b[j]说明当前元素可以加入LCSdp[i][j] dp[i-1][j-1] 1如果a[i] ! b[j]当前元素不能同时加入取两种情况的最大值dp[i][j] max(dp[i-1][j], dp[i][j-1])4.3 代码实现n,mmap(int,input().split())a[0]list(map(int,input().split()))b[0]list(map(int,input().split()))# dp[i][j]a的前i个和b的前j个的LCS长度dp[[0]*(m1)for_inrange(n1)]foriinrange(1,n1):forjinrange(1,m1):ifa[i]b[j]:dp[i][j]dp[i-1][j-1]1else:dp[i][j]max(dp[i-1][j],dp[i][j-1])print(dp[n][m])# 如果需要输出LCS序列可以回溯defget_lcs():ans[]x,yn,mwhilex!0andy!0:ifdp[x][y]dp[x-1][y]:# 来自上方a[x]不在LCS中x-1elifdp[x][y]dp[x][y-1]:# 来自左方b[y]不在LCS中y-1else:# 来自左上方a[x] b[y]在LCS中ans.append(a[x])x-1y-1returnans[::-1]# 反转得到正序# print(get_lcs())4.4 回溯输出LCS如果题目要求输出LCS序列本身需要从dp[n][m]往回走如果dp[x][y] dp[x-1][y]说明 a[x] 不在LCS中往上走如果dp[x][y] dp[x][y-1]说明 b[y] 不在LCS中往左走否则a[x] b[y]这个元素在LCS中加入答案往左上走最后把答案反转得到正序的LCS。4.5 踩坑记录下标从1开始a[0]和b[0]是占位符实际数据从1开始dp数组大小(n1) x (m1)多一行一列作为边界全0相等时的转移dp[i-1][j-1] 1不是dp[i][j-1] 1或dp[i-1][j] 1回溯时的方向先判断上方和左方最后才判断左上方五、第四题数字三角形难度⭐⭐⭐5.1 题目大意给定一个数字三角形从顶部出发每次可以走到左下方或右下方的相邻位置求到达底部的最大路径和。5.2 解题思路这道题有两种DP思路都很经典法1自底向上dp[i][j]表示从 (i,j) 出发到底部的最大和状态转移dp[i][j] max(dp[i1][j], dp[i1][j1]) a[i][j]最终答案dp[1][1]法2自顶向下dp[i][j]表示从顶部到达 (i,j) 的最大和状态转移dp[i][j] max(dp[i-1][j], dp[i-1][j-1]) a[i][j]最终答案max(dp[n])两种方法都可以自顶向下更符合直觉自底向下不需要处理边界。5.3 代码实现法1自顶向下nint(input())a[[0]*(n1)]for_inrange(n):a.append([0]list(map(int,input().split())))# dp[i][j]到达(i,j)的最大和dp[[0]*(n1)for_inrange(n1)]foriinrange(1,n1):forjinrange(1,i1):# 第i行有i个数字dp[i][j]max(dp[i-1][j],dp[i-1][j-1])a[i][j]print(max(dp[n]))5.4 代码实现法2自底向上nint(input())a[[0]*(n1)]for_inrange(n):a.append([0]list(map(int,input().split())))dp[[0]*(n1)for_inrange(n1)]# 从下往上递推foriinrange(n,0,-1):forjinrange(1,i1):ifin:# 最底行初始值就是a的值dp[i][j]a[i][j]else:dp[i][j]max(dp[i1][j],dp[i1][j1])a[i][j]print(dp[1][1])5.5 踩坑记录输入处理每行数字个数不同第 i 行有 i 个数字下标从1开始a[0]是占位行每行第一个元素也是占位自顶向下的边界dp[i-1][j]和dp[i-1][j-1]当 j1 时dp[i-1][0]0不影响结果最终答案自顶向下取max(dp[n])自底向上取dp[1][1]六、第五题摆花难度⭐⭐⭐⭐6.1 题目大意有 n 种花第 i 种花最多有 a[i] 盆。要从中选出 m 盆花摆成一排每种花可以选 0 盆、1 盆、…、最多 a[i] 盆。问有多少种选法。6.2 解题思路这道题是多重背包的变形也可以看作组合计数的DP。状态定义dp[i][j]表示前 i 种花选出 j 盆的方案数。状态转移对于第 i 种花可以选择 0 盆、1 盆、…、min(a[i], j) 盆。dp[i][j] dp[i-1][j] dp[i-1][j-1] dp[i-1][j-2] ... dp[i-1][j-min(a[i],j)]6.3 代码实现n,mmap(int,input().split())a[0]list(map(int,input().split()))# dp[i][j]前i种花选j盆的方案数dp[[0]*(m1)for_inrange(n1)]# 边界选0盆花任何情况下都只有1种方案什么都不选foriinrange(n1):dp[i][0]1mod10**67foriinrange(1,n1):forjinrange(1,m1):# 枚举第i种花选k盆forkinrange(min(a[i],j)1):dp[i][j]dp[i-1][j-k]dp[i][j]%modprint(dp[n][m])6.4 状态转移详解对于dp[i][j]第 i 种花可以选 0 到min(a[i], j)盆选 0 盆前 i-1 种花选 j 盆方案数dp[i-1][j]选 1 盆前 i-1 种花选 j-1 盆方案数dp[i-1][j-1]…选 k 盆前 i-1 种花选 j-k 盆方案数dp[i-1][j-k]把这些全部加起来就是dp[i][j]。6.5 优化前缀和优化上面的代码时间复杂度是 O(n * m * max(a[i]))如果数据范围大可能会超时。可以用前缀和优化到 O(n * m)# 前缀和优化版本foriinrange(1,n1):# 先计算前缀和prefix[0]*(m2)forjinrange(m1):prefix[j1](prefix[j]dp[i-1][j])%modforjinrange(1,m1):# dp[i][j] sum(dp[i-1][j-k]) for k in 0..min(a[i],j)# prefix[j1] - prefix[j-min(a[i],j)]k_maxmin(a[i],j)dp[i][j](prefix[j1]-prefix[j-k_max])%mod6.6 踩坑记录边界条件dp[i][0] 1选0盆花只有一种方案取模每一步都要取模防止溢出k的范围range(min(a[i], j) 1)不能超过 j总共只要 j 盆数组大小(n1) x (m1)下标从0开始七、今日总结题目核心模型状态定义状态转移时间复杂度LIS线性DPdp[i]以i结尾的LIS长度dp[i] max(dp[j]1), ji,a[j]a[i]O(n²)合唱队形LISLDSdp1正序dp2逆序枚举最高点合并O(n²)LCS二维DPdp[i][j]前i前j的LCS相等1不等取maxO(nm)数字三角形递推DPdp[i][j]到达/出发的最大和左上/右上取maxO(n²)摆花多重背包dp[i][j]前i种选j盆的方案数枚举第i种选几盆O(nma)今天这五道题覆盖了动态规划的五大经典模型LIS最长上升子序列线性DP的入门LDS最长下降子序列LIS的反向应用LCS最长公共子序列二维DP的模板数字三角形递推DP自顶向下或自底向上多重背包组合计数枚举前缀和优化建议把这五道题的代码都背下来考场上遇到同类题目直接改数据就行。特别是LIS和LCS几乎是每场蓝桥杯必考的。明天继续肝真题兄弟们一起加油八、附录DP模板速查LIS模板dp[1]*(n1)foriinrange(1,n1):forjinrange(1,i):ifa[j]a[i]:dp[i]max(dp[i],dp[j]1)LCS模板dp[[0]*(m1)for_inrange(n1)]foriinrange(1,n1):forjinrange(1,m1):ifa[i]b[j]:dp[i][j]dp[i-1][j-1]1else:dp[i][j]max(dp[i-1][j],dp[i][j-1])数字三角形模板自顶向下foriinrange(1,n1):forjinrange(1,i1):dp[i][j]max(dp[i-1][j],dp[i-1][j-1])a[i][j]如果觉得有帮助欢迎点赞收藏有问题评论区见
备战蓝桥杯国赛【Day 27】
一、写在前面兄弟们Day 27今天一口气刷了五道动态规划的经典模型题每一道都是蓝桥杯考场上必考必会的题型。从最基础的LIS到多重背包从数字三角形到最长公共子序列这些模板如果能在考场上直接默写出来至少能省下20分钟。今天的五道题最长上升子序列(LIS) —— 线性DP入门合唱队形 —— LIS正序逆序最长公共子序列(LCS) —— 二维DP经典数字三角形 —— 递推DP摆花 —— 多重背包二、第一题最长上升子序列难度⭐⭐⭐2.1 题目大意给定一个长度为 n 的序列求最长的严格上升子序列的长度。2.2 解题思路这是最经典的动态规划模型之一。状态定义dp[i]表示以第 i 个数字结尾的最长上升子序列的长度。状态转移对于每个 i枚举前面的所有 jj i如果a[j] a[i]说明 a[i] 可以接在 a[j] 后面更新dp[i] max(dp[i], dp[j] 1)。最终答案max(dp)因为最长上升子序列的结尾不一定在哪个位置。2.3 代码实现nint(input())a[0]list(map(int,input().split()))# 下标从1开始dp[0]*(n1)foriinrange(1,n1):# 至少包含自己长度为1dp[i]1# 在i的前面找小于a[i]的数字forjinrange(1,i):ifa[j]a[i]:dp[i]max(dp[i],dp[j]1)print(max(dp))2.4 时间复杂度分析时间复杂度O(n²)双重循环空间复杂度O(n)对于 n ≤ 10⁵ 的数据会超时需要用到二分优化 patience sorting 算法时间复杂度降到 O(n log n)。但蓝桥杯大部分题目 n ≤ 1000O(n²) 完全够用。2.5 踩坑记录下标从1开始a [0] list(...)这样 a[1] 就是第一个元素方便处理初始状态dp[i] 1每个元素至少可以单独成一个子序列最终答案取max(dp)不是dp[n]严格上升条件是不是三、第二题合唱队形难度⭐⭐⭐⭐3.1 题目大意N 位同学站成一排音乐老师要请其中的 N-K 位同学出列使得剩下的 K 位同学排成合唱队形。合唱队形是指设 K 位同学从左到右依次编号为 1,2,…,K他们的身高分别为 T1,T2,…,TK则 T1 T2 … Ti且 Ti Ti1 … TK1 ≤ i ≤ K。也就是说合唱队形是一个先严格上升再严格下降的序列。求最少需要出列多少位同学。3.2 解题思路这道题是LIS的变形。对于每个位置 i我们需要知道dp1[i]以 i 结尾的最长上升子序列长度从左往右dp2[i]从 i 开始的最长下降子序列长度从右往左然后枚举每个位置 i 作为最高点以 i 为最高点的合唱队形长度 dp1[i] dp2[i] - 1i 被算了两次减1。最终答案n - max(dp1[i] dp2[i] - 1)3.3 代码实现nint(input())a[0]list(map(int,input().split()))# dp1[i]以i结尾的最长上升子序列长度正序dp1[0][1]*nforiinrange(1,n1):forjinrange(1,i):ifa[j]a[i]:dp1[i]max(dp1[i],dp1[j]1)# dp2[i]从i开始的最长下降子序列长度逆序dp2[0][1]*nforiinrange(n,0,-1):forjinrange(i1,n1):ifa[i]a[j]:# 注意这里是下降所以是 dp2[i]max(dp2[i],dp2[j]1)# 枚举最高点求最大合唱队形长度ansmax([dp1[i]dp2[i]-1foriinrange(1,n1)])print(n-ans)3.4 关键技巧正序LIS从左往右递推找前面比当前小的逆序LDS从右往左递推找后面比当前小的等价于从右往左的LIS合并时减1最高点被两个DP数组各算了一次要去重3.5 踩坑记录dp2的递推方向从右往左range(n, 0, -1)dp2的比较条件a[i] a[j]因为要找下降的最终答案n - ans不是ans题目问的是最少出列多少人列表推导式[dp1[i] dp2[i] - 1 for i in range(1, n 1)]简洁高效四、第三题最长公共子序列难度⭐⭐⭐⭐4.1 题目大意给定两个序列 A 和 B求它们的最长公共子序列LCS的长度。如果需要还要输出这个子序列。4.2 解题思路二维DP的经典模型。状态定义dp[i][j]表示 A 的前 i 个元素和 B 的前 j 个元素的最长公共子序列长度。状态转移如果a[i] b[j]说明当前元素可以加入LCSdp[i][j] dp[i-1][j-1] 1如果a[i] ! b[j]当前元素不能同时加入取两种情况的最大值dp[i][j] max(dp[i-1][j], dp[i][j-1])4.3 代码实现n,mmap(int,input().split())a[0]list(map(int,input().split()))b[0]list(map(int,input().split()))# dp[i][j]a的前i个和b的前j个的LCS长度dp[[0]*(m1)for_inrange(n1)]foriinrange(1,n1):forjinrange(1,m1):ifa[i]b[j]:dp[i][j]dp[i-1][j-1]1else:dp[i][j]max(dp[i-1][j],dp[i][j-1])print(dp[n][m])# 如果需要输出LCS序列可以回溯defget_lcs():ans[]x,yn,mwhilex!0andy!0:ifdp[x][y]dp[x-1][y]:# 来自上方a[x]不在LCS中x-1elifdp[x][y]dp[x][y-1]:# 来自左方b[y]不在LCS中y-1else:# 来自左上方a[x] b[y]在LCS中ans.append(a[x])x-1y-1returnans[::-1]# 反转得到正序# print(get_lcs())4.4 回溯输出LCS如果题目要求输出LCS序列本身需要从dp[n][m]往回走如果dp[x][y] dp[x-1][y]说明 a[x] 不在LCS中往上走如果dp[x][y] dp[x][y-1]说明 b[y] 不在LCS中往左走否则a[x] b[y]这个元素在LCS中加入答案往左上走最后把答案反转得到正序的LCS。4.5 踩坑记录下标从1开始a[0]和b[0]是占位符实际数据从1开始dp数组大小(n1) x (m1)多一行一列作为边界全0相等时的转移dp[i-1][j-1] 1不是dp[i][j-1] 1或dp[i-1][j] 1回溯时的方向先判断上方和左方最后才判断左上方五、第四题数字三角形难度⭐⭐⭐5.1 题目大意给定一个数字三角形从顶部出发每次可以走到左下方或右下方的相邻位置求到达底部的最大路径和。5.2 解题思路这道题有两种DP思路都很经典法1自底向上dp[i][j]表示从 (i,j) 出发到底部的最大和状态转移dp[i][j] max(dp[i1][j], dp[i1][j1]) a[i][j]最终答案dp[1][1]法2自顶向下dp[i][j]表示从顶部到达 (i,j) 的最大和状态转移dp[i][j] max(dp[i-1][j], dp[i-1][j-1]) a[i][j]最终答案max(dp[n])两种方法都可以自顶向下更符合直觉自底向下不需要处理边界。5.3 代码实现法1自顶向下nint(input())a[[0]*(n1)]for_inrange(n):a.append([0]list(map(int,input().split())))# dp[i][j]到达(i,j)的最大和dp[[0]*(n1)for_inrange(n1)]foriinrange(1,n1):forjinrange(1,i1):# 第i行有i个数字dp[i][j]max(dp[i-1][j],dp[i-1][j-1])a[i][j]print(max(dp[n]))5.4 代码实现法2自底向上nint(input())a[[0]*(n1)]for_inrange(n):a.append([0]list(map(int,input().split())))dp[[0]*(n1)for_inrange(n1)]# 从下往上递推foriinrange(n,0,-1):forjinrange(1,i1):ifin:# 最底行初始值就是a的值dp[i][j]a[i][j]else:dp[i][j]max(dp[i1][j],dp[i1][j1])a[i][j]print(dp[1][1])5.5 踩坑记录输入处理每行数字个数不同第 i 行有 i 个数字下标从1开始a[0]是占位行每行第一个元素也是占位自顶向下的边界dp[i-1][j]和dp[i-1][j-1]当 j1 时dp[i-1][0]0不影响结果最终答案自顶向下取max(dp[n])自底向上取dp[1][1]六、第五题摆花难度⭐⭐⭐⭐6.1 题目大意有 n 种花第 i 种花最多有 a[i] 盆。要从中选出 m 盆花摆成一排每种花可以选 0 盆、1 盆、…、最多 a[i] 盆。问有多少种选法。6.2 解题思路这道题是多重背包的变形也可以看作组合计数的DP。状态定义dp[i][j]表示前 i 种花选出 j 盆的方案数。状态转移对于第 i 种花可以选择 0 盆、1 盆、…、min(a[i], j) 盆。dp[i][j] dp[i-1][j] dp[i-1][j-1] dp[i-1][j-2] ... dp[i-1][j-min(a[i],j)]6.3 代码实现n,mmap(int,input().split())a[0]list(map(int,input().split()))# dp[i][j]前i种花选j盆的方案数dp[[0]*(m1)for_inrange(n1)]# 边界选0盆花任何情况下都只有1种方案什么都不选foriinrange(n1):dp[i][0]1mod10**67foriinrange(1,n1):forjinrange(1,m1):# 枚举第i种花选k盆forkinrange(min(a[i],j)1):dp[i][j]dp[i-1][j-k]dp[i][j]%modprint(dp[n][m])6.4 状态转移详解对于dp[i][j]第 i 种花可以选 0 到min(a[i], j)盆选 0 盆前 i-1 种花选 j 盆方案数dp[i-1][j]选 1 盆前 i-1 种花选 j-1 盆方案数dp[i-1][j-1]…选 k 盆前 i-1 种花选 j-k 盆方案数dp[i-1][j-k]把这些全部加起来就是dp[i][j]。6.5 优化前缀和优化上面的代码时间复杂度是 O(n * m * max(a[i]))如果数据范围大可能会超时。可以用前缀和优化到 O(n * m)# 前缀和优化版本foriinrange(1,n1):# 先计算前缀和prefix[0]*(m2)forjinrange(m1):prefix[j1](prefix[j]dp[i-1][j])%modforjinrange(1,m1):# dp[i][j] sum(dp[i-1][j-k]) for k in 0..min(a[i],j)# prefix[j1] - prefix[j-min(a[i],j)]k_maxmin(a[i],j)dp[i][j](prefix[j1]-prefix[j-k_max])%mod6.6 踩坑记录边界条件dp[i][0] 1选0盆花只有一种方案取模每一步都要取模防止溢出k的范围range(min(a[i], j) 1)不能超过 j总共只要 j 盆数组大小(n1) x (m1)下标从0开始七、今日总结题目核心模型状态定义状态转移时间复杂度LIS线性DPdp[i]以i结尾的LIS长度dp[i] max(dp[j]1), ji,a[j]a[i]O(n²)合唱队形LISLDSdp1正序dp2逆序枚举最高点合并O(n²)LCS二维DPdp[i][j]前i前j的LCS相等1不等取maxO(nm)数字三角形递推DPdp[i][j]到达/出发的最大和左上/右上取maxO(n²)摆花多重背包dp[i][j]前i种选j盆的方案数枚举第i种选几盆O(nma)今天这五道题覆盖了动态规划的五大经典模型LIS最长上升子序列线性DP的入门LDS最长下降子序列LIS的反向应用LCS最长公共子序列二维DP的模板数字三角形递推DP自顶向下或自底向上多重背包组合计数枚举前缀和优化建议把这五道题的代码都背下来考场上遇到同类题目直接改数据就行。特别是LIS和LCS几乎是每场蓝桥杯必考的。明天继续肝真题兄弟们一起加油八、附录DP模板速查LIS模板dp[1]*(n1)foriinrange(1,n1):forjinrange(1,i):ifa[j]a[i]:dp[i]max(dp[i],dp[j]1)LCS模板dp[[0]*(m1)for_inrange(n1)]foriinrange(1,n1):forjinrange(1,m1):ifa[i]b[j]:dp[i][j]dp[i-1][j-1]1else:dp[i][j]max(dp[i-1][j],dp[i][j-1])数字三角形模板自顶向下foriinrange(1,n1):forjinrange(1,i1):dp[i][j]max(dp[i-1][j],dp[i-1][j-1])a[i][j]如果觉得有帮助欢迎点赞收藏有问题评论区见
