动态规划--最长上升子序列(LIS)的长度
l例如:对于[3,1,4,2,5],最长上升子序列的长度是3
arr = [3,1,4,5,9,2,6,5,0] def lis(arr): #dp[i]表示第i个位置的值为尾的数组的最长递增子序列的长度 #初始化数组,假定数组中每个值的最长子序列就是它自己,即都是1 dp = [1 for _ in range(len(arr))] #遍历数组 for i in range(len(arr)): #当遍历到第i个位置时,再依次从0开始遍历到 for j in range(i): #如果第i个位置的值比第j个位置的值要大,那么长度就是max(dp[j]+1,dp[i]) if arr[i]>arr[j]: dp[i]=max(dp[i],dp[j]+1) return dp
最后输出dp:
[1,1,2,3,4,2,4,3,1]
版权声明:本文为xiximayou原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。