算法第四十三天：动态规划第四十三天part10（第九章）

1.最长递增子序列

 思路：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        #dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
        dp = [1] *len(nums)
        result = 1
        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)
            result = max(result, dp[i])
        return result

        

2.最长连续递增序列

674. 最长连续递增序列 - 力扣（LeetCode）

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        #dp[i] 表示以nums[i]结尾的最长且连续递增的子序列
        #dp[i] = dp[i - 1] + 1;
        if len(nums) == 0:
            return 0
        dp = [1] * len(nums)
        result = 1
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:#连续记录
                dp[i] = dp[i-1]+1
            result = max(dp[i], result)
        return result
        

3.最长重复子数组

718. 最长重复子数组 - 力扣（LeetCode）

核心思路：动态规划（DP）

1. 状态定义

   • dp[i][j] 表示：
     以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组的长度。

2. 状态转移

   • 如果 nums1[i-1] == nums2[j-1]：

     dp[i][j]=dp[i−1][j−1]+1dp[i][j] = dp[i-1][j-1] + 1dp[i][j]=dp[i−1][j−1]+1

   • 如果不相等：

     dp[i][j]=0dp[i][j] = 0dp[i][j]=0

     因为连续性被打断。

3. 初始化

   • 第一行、第一列全部为 0（额外加一行一列的 0，避免越界）。

4. 结果记录

   • 用变量 result 保存遍历过程中遇到的最大 dp[i][j] 值。

复杂度分析

• 时间复杂度：O(m×n)O(m \times n)O(m×n)
  mmm 和 nnn 分别为两个数组的长度。

• 空间复杂度：O(m×n)O(m \times n)O(m×n)
  可通过滚动数组优化到 O(min⁡(m,n))O(\min(m, n))O(min(m,n))。

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        #用dp[i][j] 表示以nums1[i-1],nums2[j-1]结尾的最长公共子数组的长度, 不是全局最大值，所以要定义result来记录
        #如果nums1[i-1]=nums2[j-1],那么：dp[i][j] = dp[i-1][j-1]+1
        
        #初始化
        m = len(nums1)
        n = len(nums2)
        dp = [[0] * (n+1) for _ in range(m+1)]
        result = 0

        #
        for i in range(1, m+1):
            for j in range(1, n+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
        
                

结束！