2. # 子列， 不是子串
  4. # dp[i]：以i结尾的最长递增字串
  5. def LengthOfLIS(nums: [int]) -> int:
  6.     dp = [1 for i in range(len(nums))]
  8.     for i in range(len(nums)):
  9.         for j in range(i):
  10.             if nums[i] > nums[j]:
  11.                 # 状态转移方程
  12.                 dp[i] = max(dp[i], dp[j] + 1)
  13.     print(dp)
  14.     return max(dp)
  17. # 朴素, dp[i]: i之前的最长递增字串
  18. def BruteLengthOfLIS(nums: [int]) -> int:
  20.     max_end_of_i = [1 for i in range(len(nums))]
  21.     dp = [1 for i in range(len(nums))]
  22.     for i in range(len(nums)):
  23.         for j in range(i):
  24.             if nums[i] > nums[j]:
  25.                 max_end_of_i[i] = max(max_end_of_i[i], max_end_of_i[j] + 1)
  27.     for i in range(1, len(nums)):
  28.         dp[i] = max(dp[i - 1], max_end_of_i[i])
  29.     print(dp)
  30.     return dp[-1]
  31. target = [10, 9, 2, 5, 3, 7, 101, 18]
  33. print(LengthOfLIS(target))
  34. print(BruteLengthOfLIS(target))

总结

  • dp的含义不一定直接就是问题的解， 有时候dp是间接的， dp定义需要谨慎