132. 分割回文串 II

• 思路
  • example
  • 最少分割次数
    • 分为两步骤

dp[i][j], 区间DP， s[i,...,j]是否回文串
f[i]: 以ith结尾的子串的 最少分割次数
f[i] = min(f[i], f[j] + 1), 如果s[j+1,...,i]是回文串 （相当于枚举最后一个分割位置）

• 复杂度. 时间：, 空间:

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s)  
        dp = [[True] * n for _ in range(n)]
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
        f = [n+1] * n
        f[0] = 0   
        for i in range(1, n):
            if dp[0][i] == True:
                f[i] = 0 # no need to cut
            else: # 枚举最后一cut的位置: j后面
                for j in range(i):
                    if dp[j+1][i] == True:
                        f[i] = min(f[i], f[j] + 1)
        return f[n-1]

class Solution:
    def minCut(self, s: str) -> int:
        n = len(s) 
        # Step 1: dp[i][j]
        dp = [[False for _ in range(n)] for _ in range(n)] 
        for i in range(n-1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j]:
                    if j - i <= 1:
                        dp[i][j] = True 
                    else:
                        dp[i][j] = dp[i+1][j-1] 
                else:
                    dp[i][j] = False 
        # Step 2: f[i] = min(f[i], f[j]+1) if dp[j+1][i] == True 
        f = [n-1 for _ in range(n)]
        f[0] = 0 
        for i in range(1, n):
            if dp[0][i] == True: # !!!
                f[i] = 0 # no need to cut
            else:
                for j in range(i):
                    if dp[j+1][i] == True:
                        f[i] = min(f[i], f[j] + 1)
        return f[n-1]

673. 最长递增子序列的个数

• 思路
  • example
  • 复习 LIS: #300 长度
    • 常规单串DP, 时间

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        dp[0] = 1
        for i in range(1, len(nums)):
            dp[i] = 1
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

• 二分优化 时间：, 空间:

d[i]: 长度为i的LIS的最后一个元素的最小可能值。这样就能构造尽可能长的递增子序列。
初始化d[0] = float('-inf')
d是严格递增的

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def BinarySearch_insert(d, target): # 第一个>=位置，左边界
            left, right = 0, len(d)-1
            while left <= right:
                mid = left + (right - left) // 2
                if d[mid] > target:
                    right = mid - 1
                elif d[mid] < target:
                    left = mid + 1
                else: # nums[mid] == target
                    right = mid - 1
            return left  # it's possible to have left = len(d) + 1
        n = len(nums)
        d = [float('-inf')]
        res = 0
        for i in range(n):
            # 在d中找最小的index使得d[index] >= nums[i], 二分找左边界
            insert_idx = BinarySearch_insert(d, nums[i])
            if insert_idx == len(d):
                d.append(nums[i])
                res += 1
            else:
                d[insert_idx] = nums[i]
        return res

• d[i]: 长度为i+1的LIS的最后一个元素的最小可能值。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        def BinarySearch(nums, target):
            n = len(nums)
            left, right = 0, n-1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return left 
        n = len(nums)
        stack = [] # [nums[0]]
        for i in range(n):
            idx = BinarySearch(stack, nums[i]) 
            if idx == len(stack):
                stack.append(nums[i]) 
            else:
                stack[idx] = nums[i] 
        return len(stack) 

• 这里#673 目标：个数

dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度
cnt[i] 表示以 nums[i] 结尾的最长上升子序列的个数
目标：sum(cnt[i] if dp[i] == max_length)

• 复杂度. 时间：, 空间:

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n  # 以i结尾最长LIS的长度
        cnt = [1] * n # 以i结尾最长LIS的个数
        max_length = 1 # 最长LIS的长度
        for i in range(1, n):
            for j in range(i): 
                if nums[i] > nums[j]:
                    if dp[j]+1 > dp[i]: # 更新以i结尾的最长LIS的 长度/个数
                        dp[i] = dp[j] + 1
                        cnt[i] = cnt[j]
                    elif dp[j]+1 == dp[i]:
                        # dp[i] = dp[j] + 1 # 可省去这行，因为以i结尾的最长LIS 没有变化 
                        cnt[i] += cnt[j]
                    # else: 不需要考虑
            if dp[i] > max_length:
                max_length = dp[i]
        # 最后统计累加
        res = 0
        for i in range(n):
            if dp[i] == max_length:
                res += cnt[i]
        return res 

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        # dp[i] 长度
        # cnt[i] 个数
        n = len(nums) 
        dp = [1 for _ in range(n)] 
        cnt = [1 for _ in range(n)]
        # Step 1: update dp[i] and cnt[i]
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[j]+1 > dp[i]:
                        cnt[i] = cnt[j] 
                    elif dp[j]+1 == dp[i]:
                        cnt[i] += cnt[j] 
                    dp[i] = max(dp[i], dp[j]+1)
        max_ = max(dp) 
        # Step 2 
        res = 0
        for i in range(n): 
            if dp[i] == max_:
                res += cnt[i] 
        return res 

• 二分优化

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        # d[i] = [*, *, *], both d (increasing) and d[i] (decreasing) are ordered, keep history
        # https://leetcode.cn/problems/number-of-longest-increasing-subsequence/solutions/1007075/zui-chang-di-zeng-zi-xu-lie-de-ge-shu-by-w12f/
        # cnt[i][j]: 以数字d[i][j]结尾的LIS的个数，目标cnt[n-1][-1]. 实际：前缀和
        def bisect(start, end, func):
            left, right = start, end 
            while left <= right:
                mid = left + (right - left) // 2
                if func(mid): 
                    right = mid - 1
                else:
                    left = mid + 1
            return left 
        n = len(nums) 
        d, cnt = [], [] 
        d = []
        for num in nums:
            idx = bisect(0, len(d)-1, lambda x: d[x][-1] >= num) 
            c = 1
            if idx > 0:
                idx2 = bisect(0, len(d[idx-1])-1, lambda x: d[idx-1][x] < num)
                c = cnt[idx-1][-1] - cnt[idx-1][idx2] 
            if idx == len(d):
                d.append([num]) 
                cnt.append([0, c]) 
            else: 
                d[idx].append(num) 
                cnt[idx].append(cnt[idx][-1] + c)
        return cnt[-1][-1]