算法day52|300,674,718

Source

52 第八章 动态规划

  • 300.最长递增子序列
  • 674. 最长连续递增序列
  • 718. 最长重复子数组

详细布置

300.最长递增子序列

dp数组的定义

dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度

nums = [10,9,2,5,3,7,101,18]

相当于nums[4] ,以3为结尾(该序列长度为4),最长上升子序列的长度为2

dp[j]指的是j从(0到4-1)各个位置的最长升序子序列 + 1 的最大值。

状态转移方程

if语句的意思是:找到升序的地方.Eg:[10,9,2,5,3,7,101,18],找到5,下标为3。

if (nums[i] > nums[j])

dp[i] = max(dp[i], dp[j] + 1);

所以dp[j]+1就相当于dp[i],他们两个是一样的

max的作用不是比较大小

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)
        dp = [1] * len(nums)
        result = 0
        for i in range(1, len(nums)):
            for j in range(0, i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
            if dp[i]>result:            
                result = dp[i] #取长的子序列
        return result

代码随想录

674. 最长连续递增序列

这个简单一点

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        #dp数组中及含义
        dp = [1]*len(nums)
        result = 1
        #遍历顺序
        for i in range(0,len(nums)-1):
            #递归公式
            if nums[i+1]>nums[i]:
                dp[i+1] = dp[i]+1
            if dp[i+1]>result:
                result = dp[i+1]
        return result

连续的话只用比较前面的数是不是大的,连续的话就存储,比不连续的简单

代码随想录

718. 最长重复子数组

​​​​​​​

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        #dp初始化
        dp = [[0 for _ in range(len(nums1)+1)] for _ in range(len(nums2)+1)]
        print(dp)
        result =0
        #初始化,都没有意义,所以都初始化为0
        #遍历顺序
        for i in range(1,len(nums1)+1):
            for j in range(1,len(nums2)+1):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                if dp[i][j] >result:
                    result = dp[i][j]
        return result

稍有难度,要使用二维dp数组了

代码随想录