动态规划——最长递增子序列系列问题（python）

总述：

这些系列问题都是，遍历当前元素，然后去找当前元素的前驱元素（即不能超过当前元素的下标）。有的问题需要先排序，有的不需要。

即：

for i in range(len(nums)):

for j in range(i):

1.最长递增子序列：

如：nums = [10,9,2,5,3,7,101,18] 最长递增子序列为2 3 7 10 长度为4.

dp数组定义:dp[i]表示以nums[i]为结尾的最长递增子序列长度为dp[i]

dp初始化：dp=[1]*(len(nums)) 每个元素的初始序列长度都为1

条件：if nums[i]>nums[j]

状态转移：dp[i]=max(dp[i],dp[j]+1)

def lengthOfLIS(nums): n=len(nums) dp=[1]*n #初始化，以每个元素结尾的初始长度都为1 for i in range(n): #遍历当前元素 for j in range(i): #遍历当前元素的所有前驱元素 if nums[i]>nums[j]: dp[i]=max(dp[i],dp[j]+1) return max(dp) if dp else 0 def main(): nums=list(map(int,input().split())) res=lenghthOfLIS(nums) print(res) if __name__=="__main__": main()

2.俄罗斯套娃信封问题

求信封的最大个数。只有当高度和宽度都大于另一个信封的时候，才能将该信封装进去。如：envelopes = [[5,4],[6,4],[6,7],[2,3]] 最多信封个数为3。首先，这里需要排序。

排序：envelpoes.sort(key=lambda x:(x[0],-x[1]))

dp数组定义：dp[i]表示以前i个信封为底的时候，高度为dp[i]

dp数组初始化：dp=[1]*(n) 对于每一个信封，初始数量为一个

条件：if cur_h>pre_h and cur_w>pre_w:

状态转移：dp[i]=max(dp[i],dp[j]+1)

该算法只能通过90%样例，因为O(n^2)会超时。优化需要用二分查找。

def maxEnvelopes(nums): n=len(nums) nums.sort(key=lambda x:(x[0],-x[1])) #先排序，如果宽度一样，高度倒序排序 dp=[1]*n for i in range(n): #遍历当前信封 cur_w,cur_h=nums[i] for j in range(i): #遍历前驱信封 pre_w,pre_h=nums[j] if cur_h>pre_h and cur_w>pre_w: dp[i]=max(dp[i],dp[j]+1) return max(dp) if dp else 0 def main(): nums= [[5,4],[6,4],[6,7],[2,3]] res=maxEnvelopes(nums) print(res) if __name__=="__main__": main()

3.堆叠长方体的最大高度

如果一个长方体的长宽高都小于等于第i个长方体，那么就可以堆在它上面。这里可以通过旋转重新排列长方体的长宽高，求可以堆叠的最大高度。

排序：for c in cuboids: c.sort() 重排长宽高

再次排序：cuboids.sort()

dp数组定义：前i个长方体堆叠的最大高度为dp[i]

dp数组初始化：dp=[item[2] for item in cuboids] 初始化为每个长方体的高度

条件：if cur_l>=pre_l and cur_w>=pre_w and cur_h>=pre_h

状态转移：dp[i]=max(dp[i],dp[j]+cur_h)

def maxHeight(cuboids): n=len(cuboids ) for c in cuboids: c.sort() cuboids.sort() dp=[item[2] for item in cuboids] for i in range(n): cur_l,cur_w,cur_h=cuboids[i] for j in range(i): pre_l,pre_w,pre_h=cuboids[j] if cur_w>=pre_w and cur_l>=pre_l and cur_h>=pre_h: dp[i]=max(dp[i],dp[j]+cur_h) return max(dp) if dp else 0 def main(): cuboids = [[50, 45, 20], [95, 37, 53], [45, 23, 12]] res=maxHeight(cuboids) print(res) if __name__=="__main__": main()

4.盒子的最大高度

也是求最大高度，和上一题求长方体最大高度类似，只不过这题不能重排长宽高。同时长宽高必须严格大于才能堆叠。首先依旧得排序。

排序：nums.sort() 这里进行了升序排列，所以越往后面越大，在后面条件判断时，就是大于

dp数组定义：前i个盒子堆起来的最大高度为dp[i]

dp数组初始化：dp=[item[2] for item in nums] 初始化为每个盒子自身的高度

条件：if cur_l>pre_l and cur_w>pre_w and cur_h>pre_h

状态转移：dp=max(dp[i],dp[j]+cur_h)

#盒子的高度 # 4 # 1 1 1 # 2 3 4 # 3 6 7 # 4 5 6 # 输出：12 def box(n,nums): nums.sort() dp=[item[2] for item in nums] for i in range(n): #遍历当前盒子 cur_l,cur_w,cur_h=nums[i] for j in range(i): #遍历前缀盒子 pre_l,pre_w,pre_h=nums[j] #因为前面对nums从小到大排序，所以当前遍历到的i要是大的才行，所以是大于号 if cur_l>pre_l and cur_w>pre_w and cur_h>pre_h: dp[i]=max(dp[i],dp[j]+cur_h) return max(dp) if dp else 0 def main(): n=int(input()) nums=[] for i in range(n): a,b,c=map(int,input().split()) nums.append((a,b,c)) res=box(n,nums) print(res) if __name__=="__main__": main()

5.规划兼职工作的最大利润

求最大利润。

排序：按工作结束时间排序 nums.sort(key=lambda x: x[1])

dp数组定义：前i份工作可以得到的最大利润为dp[i]

dp数组初始化：dp=[item[2] for item in nums] 初始化为每份工作的利润

条件：if cur_s>=pre_e

状态转移：dp[i]=max(dp[i],dp[j]+cur_p)

#最大利润 # 4 # 1 3 50 # 2 4 10 # 3 5 40 # 3 6 70 #输出 120 def maxProfit(n,nums): nums.sort(key=lambda x:x[1]) #按结束时间排序 dp=[item[2] for item in nums] for i in range(n): cur_s,cur_e,cur_p=nums[i] for j in range(i): pre_s,pre_e,pre_p=nums[j] if cur_s>=pre_e: dp[i]=max(dp[i],dp[j]+cur_p) return max(dp) if dp else 0 def main(): n=int(input()) nums=[] for i in range(n): s,e,p=map(int,input().split()) nums.append((s,e,p)) res=maxProfit(n,nums) print(res) if __name__=="__main__": main()

6.基站的盈利

求最大盈利。首先也是排序，按照任务结束时间排序。

这份代码只能通过部分测试样例，可以使用二分查找优化。

排序：nums.sort(key=lambda x :x[1]) 按照结束时间排序

dp数组定义：完成前i个任务得到的最大利润为dp[i]

dp数组初始化：dp=[item[2] for item in nums] 初始化为每个任务的利润

条件：if cur_s >pre_e

状态转移：dp[i]=max(dp[i],dp[j]+cur_p)

#基站盈利问题 # 20 # 6 # 1 6 1 # 3 10 2 # 10 12 3 # 11 12 2 # 12 15 2 # 13 18 1 # 输出 5 def stationsProfit(m,nums): nums.sort(key=lambda x:x[1]) #按结束时间排序 dp=[item[2] for item in nums] #初始化为每个任务的利润 for i in range(m): cur_s,cur_e,cur_p=nums[i] for j in range(i): pre_s,pre_e,pre_p=nums[j] if cur_s>pre_e: dp[i]=max(dp[i],dp[j]+cur_p) return max(dp) if dp else 0 def main(): n=int(input()) m=int(input()) nums=[] for i in range(m): a,b,c=map(int,input().split()) nums.append((a,b,c)) res=stationsProfit(m,nums) print(res) if __name__=="__main__": main()