Leetcode刷题——动态规划

一维DP数组问题

解题模板

# 一维DP数组
# dp[i]为以nums[i]为结尾的目标子序列长度
for i in range(len(nums)):
    for j in range(i):
        dp[i] = 最值(dp[i],dp[j] + ...)

最长递增子序列(中等)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if nums == []: return 0
        m = len(nums)
        dp = [1 for i in range(m)] # 以nums[i]为结尾的最长递增子序列
        for i in range(1,m):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i],dp[j]+1)
        return max(dp)

更快的方法:纸牌游戏

# 二分查找——纸牌游戏
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        top = [] # 牌堆顶
        for n in nums:
            # 二分找左边界
            left,right = 0,len(top)
            while left < right:
                mid = left + (right -left) // 2
                if top[mid] == n:
                    right = mid
                elif top[mid] < n:
                    left = mid + 1
                elif top[mid] > n:
                    right = mid
            if left == len(top): # 没找到,建新堆
                top.append(n)
            else:
                top[left] = n
        return len(top)

二维DP数组问题

解题模板

# 二维DP数组
# 1. dp[i][j]为s1[0...i-1]和s2[0...j-1]中的目标子序列(最长公共子序列、编辑距离)
# 2. dp[i][j]为s[i...j]中的目标子序列(最长回文子序列)
m,n = len(s1),len(s2)
dp = [[0 for j in range(n+1)] for i in range(m+1)]
... # 处理 base case
for i in range(1,m+1):
    for j in range(1,n+1):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = dp[i-1][j-1] + ...
        else:
            dp[i][j] = 最值(...)

最长公共子序列(中等)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m,n = len(text1),len(text2)
        # dp[i][j] text1[0...i-1]和text2[0...j-1]最长公共子序列
        dp = [[0 for j in range(n+1)] for i in range(m+1)]
        # basecase d[0][0] dp[0][1] dp[1][0] = 0
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        return dp[-1][-1]

发表评论