【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总（2）

# 动态规划
# 用 P(i,j)P(i,j) 表示字符串 s的第 i 到 j 个字母组成的串（下文表示成 s[i:j]）是否为回文串
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = ""
        # 枚举子串的长度 l+1
        for l in range(n):
            # 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置
            for i in range(n-l):
                j = i + l
                if l == 0:
                    dp[i][j] = True        
                elif l == 1:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j])
                if dp[i][j] and l + 1 > len(ans):
                    ans = s[i:j+1]
        return ans
                  
                  
# 中心扩展法
class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1
                  
    def longestPalindrome(self, s: str) -> str:
        # 中心扩展法，每个字符从中心往两边扩展，分奇偶
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i) # 以当前字符为中心
            left2, right2 = self.expandAroundCenter(s, i, i + 1) # 以当前字符与后面一个字符为中心
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2
        return s[start: end + 1]

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # 动态规划
        # dp[i] 表示以i结尾的最长有效括号长度，‘（’对应的一定是0
        n = len(s)
        if n == 0:
            return 0
        dp = [0] * n
        for i in range(1,n):
            # i- dp[i-1] -1是与当前')'对称的位置
            # dp[i-dp[i-1]-2] 表示与当前')'对称的位置前面的有效括号长度，需加上
            if s[i]==')' and i - dp[i-1] - 1>=0 and s[i - dp[i-1] - 1] == '(':
                dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
        return max(dp)

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # 栈来实现
        stack = [-1]
        length = 0
        max_length = 0        
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                # 栈为空，则添加当前右括号的索引入栈，为分割标识
                    stack.append(i)
                else:
                    length = i - stack[-1]
                    max_length = max(max_length, length)
        return max_length

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        # S中T出现的个数
        # dp[i][j]表示t的前i个字符串可以由s的前j个字符串组成多少个
        n = len(s) # 列
        m = len(t) # 行
        dp = [[0] * (n+1) for _ in range(m+1)]
        for j in range(n+1):
            dp[0][j] = 1
        for i in range(1,m + 1):
            for j in range(1, n + 1):
                if t[i-1] == s[j-1]:
# 对应于两种情况，s选择当前字母和不选择当前字母
# s选择当前字母dp[i-1][j-1]
# s不选择当前字母 dp[i][j-1]
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
                else:
                    dp[i][j] = dp[i][j-1]
        return dp[-1][-1]

# 动态规划
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        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][j-1],dp[i-1][j])
        return dp[-1][-1]
                  
# 递归
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # 递归
        memo = {} #备忘录
        def dp(i, j):
            if i == -1 or j == -1:
                return 0
            if (i,j) in memo:
                return memo[(i,j)]
            if text1[i] == text2[j]:
                memo[(i,j)] = dp(i-1, j-1) + 1
            else:
                memo[(i,j)] = max(dp(i-1, j), dp(i,j-1))
            return memo[(i,j)]
        return dp(len(text1)-1,len(text2)-1)

def LCS(s1,s2):
    #dp[i][j]表示以s1的i及s2的j结尾的最长公共子串长度
    #如果s1[i-1] ！= s2[j-1] 则，dp[i][j] = 0
    m = len(s1)
    n = len(s2)
    dp = [[0] *(n+1) for _ in range(m + 1)]
    maxLen = 0
    end = 0
    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] + 1
            else:
                dp[i][j] = 0
            if dp[i][j] > maxLen:
                maxLen = dp[i][j]
                end = j-1
    if maxLen == 0:
        return ''
    else:
        return s2[end - maxLen + 1:end + 1]

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        # dp[i]表示以第i个元素结尾的最长递增子序列长度
        n = len(nums)
        dp = [1 for _ in range(n)]
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i],dp[j] + 1)
        return max(dp)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # DP递推方程        
        # 存储 s1[0..i] 和 s2[0..j] 的最小编辑距离
        m = len(word1)
        n = len(word2)
        dp = [[0]*(n+1) for i in range(m+1)]
        for i in range(m+1):
            dp[i][0] = i
        for j in range(n+1):
            dp[0][j] = j
        for i in range(1, m+1):
            for j in range(1,n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j]+1,
                    dp[i][j-1]+1,
                    dp[i-1][j-1]+1)
        return dp[m][n]
# 递归写法
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
                  
        def dp(i,j):
            if i == -1:
                return j + 1
            if j == -1:
                return i + 1
            if (i,j) in memo:
                return memo[(i,j)]
            if word1[i] == word2[j]:
                memo[(i,j)] = dp(i-1,j-1)
            else:
                memo[(i,j)] = min(dp(i-1,j)+ 1,
                dp(i,j-1) + 1,
                dp(i-1,j-1) + 1)
            return memo[(i,j)]
        memo = {}
        res = dp(len(word1)-1,len(word2)-1)
        return res

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        # p[i][j] 表示 A[i:] 和 B[j:] 的最长公共前缀，那么答案即为所有 dp[i][j] 中的最大值。
        # 如果 A[i] == B[j]，那么 dp[i][j] = dp[i + 1][j + 1] + 1，否则 dp[i][j] = 0。
        # 考虑到这里 dp[i][j] 的值从 dp[i + 1][j + 1] 转移得到，所以我们需要倒过来，首先计算 dp[len(A) - 1][len(B) - 1]，最后计算 dp[0][0]
        n, m = len(A), len(B)
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        ans = 0
        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):        
                dp[i][j] = dp[i + 1][j + 1] + 1 if A[i] == B[j] else 0
                ans = max(ans, dp[i][j])
        return ans

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = i  #最坏的情况就是全是1
            j = 1
            while i - j*j >= 0:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
        return dp[n]