动态规划part05 -- 子序列

LeetCode300. 最长递增子序列

题目链接：300. 最长递增子序列

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)

        dp = [1] * n

        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode674. 最长连续递增序列

题目链接：674. 最长连续递增序列

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        n = len(nums)

        dp = [1] * n

        for i in range(1, n):
            if nums[i] > nums[i-1]:
                dp[i] = dp[i-1] + 1

        return max(dp)
1
2
3
4
5
6
7
8
9
10
11

LeetCode718. 最长重复子数组

题目链接：718. 最长重复子数组

# n*n数组
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        length1 = len(nums1)
        length2 = len(nums2)
        result = 0

        dp = [[0 for _ in range(length1)] for _ in range(length2)]

        for i in range(length2):
            if nums2[i] == nums1[0]:
                dp[i][0] = 1
            result = max(result, dp[i][0])
        for i in range(length1):
            if nums1[i] == nums2[0]:
                dp[0][i] = 1
            result = max(result, dp[0][i])

        for i in range(1, length2):
            for j in range(1, length1):
                if nums2[i] == nums1[j]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                result = max(dp[i][j], result)

        return result
    
# (n+1)*(n+1)数组，可以省去初始化的步骤
class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        length1 = len(nums1)
        length2 = len(nums2)
        result = 0

        dp = [[0 for _ in range(length1 + 1)] for _ in range(length2 + 1)]

        for i in range(1, length2 + 1):
            for j in range(1, length1 + 1):
                if nums2[i-1] == nums1[j-1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                result = max(dp[i][j], result)

        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42