区间dp降低时间复杂度

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n=len(s)
        dp=[[0]*n for _ in range(n)]
        for i in range(n-1,-1,-1):#需要记忆
            dp[i][i]=1
            for j in range(i+1,n):
                if s[i]==s[j]:
                    dp[i][j]=dp[i+1][j-1]+2
                else:
                    dp[i][j]=max(dp[i][j-1],dp[i+1][j])
        return dp[0][n-1]

        '''
        ans=1
        #纯暴力解法O(2^N*N^2)
        for i in range(len(s)):
            s1,s2='',''
            for j in s[i:]:
                s1+=j
                s2=j+s2
                if s1==s2:
                    ans=max(ans,len(s1))
        return ans
        '''

顺序无所谓，注意规划到最外侧时的结果，区间dp从中心向外扩展

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n=len(s)
        dp=[[0]*n for _ in range(n)]
        for i in range(n):#需要记忆
            dp[i][i]=1
            for j in range(i-1,-1,-1):
                if s[i]==s[j]:
                    dp[i][j]=dp[i-1][j+1]+2
                else:
                    dp[i][j]=max(dp[i][j+1],dp[i-1][j])
        return dp[n-1][0]

image.png
关于另一个二维DP问题：两个序列的最大公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m,n=len(text1),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:
                    try:
                        dp[i][j]=max(dp[i-1][j],dp[i][j-1])
                    except:
                        print(i,j)
        return dp[m][n]

修改思路+一次过+极限内存消耗以及时间复杂度

376. 摆动序列

难度中等485 收藏 分享 切换为英文 接收动态 反馈
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为** 摆动序列 。**第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

• 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
• 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
  子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
  给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        dp_p,dp_n=1,1
        for i in range(1,len(nums)):
            if nums[i]-nums[i-1]>0:
                dp_p=dp_n+1
            elif nums[i]-nums[i-1]<0:
                dp_n=dp_p+1
        return max(dp_p,dp_n)

image.png

约瑟夫环问题的递归方程解法，当只有一个字的时候返回位置0

否则设f(n,k)即n个字k个距离最后一个的答案
易知：
f(n,k)=(f(n-1,k)+k)%k

• 即得到转移方程，使用动态规划或者递归

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        def transfer_equation(n,k):
            return 0 if n==1 else (transfer_equation(n-1,k)+k)%n
        return transfer_equation(n,k)+1

image.png

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-stack
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class MinStack:

   def __init__(self):
       """
       initialize your data structure here.
       """
       self.ds=[]
       #使用辅助栈或者多用一个变量,不可以，为了保持删除同步
       self.min_=[math.inf]#math.inf


   def push(self, val: int) -> None:
       self.ds.append(val)
       self.min_.append(min(self.min_[-1],val))



   def pop(self) -> None:
       self.ds.pop()
       self.min_.pop()


   def top(self) -> int:
       return self.ds[-1]


   def getMin(self) -> int:
       return self.min_[-1]



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

栈的用法精妙示意

给你一个由 '('、')' 和小写字母组成的字符串 s。
你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：
空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-remove-to-make-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        set_remove_idx=set()
        stack=[]
        for i in range(len(s)):
            if s[i] not in '()':
                #print('hi')
                continue
            elif s[i]=='(':
                stack.append(i)
            elif not stack:
                set_remove_idx.add(i)
            else:
                stack.pop()
        set_remove_idx=set_remove_idx.union(set(stack))
        #print(set_remove_idx)
        ans=[]
        for i,x in enumerate(s):
            if i not in set_remove_idx:
                ans.append(x)
        return ''.join(ans)

        '''
        ans,left_bracket,right_bracket=[],0,0
        for i in s:
            if i=='(':
                left_bracket+=1
                ans.append(i)
            elif i==')':
                if right_bracket<left_bracket:
                    right_bracket+=1
                    ans.append(i)
            else:
                ans.append(i)
        print(ans)
        if left_bracket>right_bracket:
            flag=[True]*len(ans)
            for i in range(len(ans)):
                if ans[i]=='(':
                    flag[i]=False
                    left_bracket-=1
                    if left_bracket==right_bracket:
                        break
            ans=[ans[i] for i  in range(len(ans)) if flag[i]]
        return ''.join(ans)
        '''

使用栈记录多余的左括号，使用集合记录多的右括号，最后union进集合。方便O(1)时间复杂度解决。