力扣https://leetcode-cn.com/problems/longest-palindromic-subsequence/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-dpzi-dv83q/

leetcode-最大最小问题-v2_MaYingColdPlay的博客-CSDN博客300. 最长上升子序列class Solution(object): def lengthOfLIS(self, nums): """ :type nums: List[int] :rtype: int """ if nums== []: return 0 dp=[1 for _ in range(len(nums))] for i in range(lhttps://blog.csdn.net/MaYingColdPlay/article/details/109143223

动态规划5部曲：

1.dp数组含义

2.递推公式

3.初始化

4.遍历顺序

5.举例推到dp数组

5.最长回文子串

动态规划

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        max_len=1
        start=0
        dp=[[0 for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i]=1
        for i in range(len(s)-1,-1,-1):
            for j in range(i+1,len(s)):
                if s[i]==s[j]:
                    if j-i+1==2:
                        dp[i][j]=True
                    else:
                        dp[i][j]=dp[i+1][j-1]
                if dp[i][j]==True:
                    cur_len=j-i+1
                    if cur_len>max_len:
                        max_len=cur_len
                        start=i
        return s[start:start+max_len]

516.最长回文子序列

动态规划

class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        #dp[i][j]=dp[i+1][j-1]+2
        #注意遍历的顺序
        dp=[[0 for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i]=1
        for i in range(len(s)-1,-1,-1):
            for j in range(i+1,len(s)):
                if s[i]==s[j]:
                    dp[i][j]=dp[i+1][j-1]+2
                else:
                    dp[i][j]=max(dp[i+1][j],dp[i][j-1])
        return dp[0][-1]

最长递增子序列

剑指offer-leetcode-最大最小问题-思路篇_MaYingColdPlay的博客-CSDN博客https://blog.csdn.net/MaYingColdPlay/article/details/106035602

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

动态规划

力扣https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/solution/python3-dong-tai-gui-hua-by-caiji-ud-xqam/

class Solution(object):
    def findNumberOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp=[1 for _ in range(len(nums))]
        cnt=[1 for _ in range(len(nums))]
        for i in range(len(nums)):
            for j in range(i):
                if nums[i]>nums[j]:
                    if dp[j]+1>dp[i]:
                        dp[i]=dp[j]+1
                        cnt[i]=cnt[j]
                    elif dp[j]+1==dp[i]:
                        cnt[i]=cnt[i]+cnt[j]
                    else:
                        continue
        res=0
        for i in range(len(nums)):
            if dp[i] == max(dp):
                res+=cnt[i]
        return res

72.编辑距离

动态规划

leetcode-买卖股票/背包问题_MaYingColdPlay的博客-CSDN博客122. 买卖股票的最佳时机 II贪心https://blog.csdn.net/MaYingColdPlay/article/details/108184505

代码随想录认准代码随想录，学习算法不迷路https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html#%E6%80%9D%E8%B7%AF

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        #其实与最长公共子序列有亿点点类似。
        #dp[i][j]表示word1[:i]和word2[:j]之间的编辑距离
        dp=[[0 for i in range(len(word2)+1)] for _ in range(len(word1)+1)]
        #初始化
        for i in range(len(word2)+1):
            dp[0][i]=i 
        for i in range(len(word1)+1):
            dp[i][0]=i
        #两层循环
        for i in range(1,len(word1)+1):
            for j in range(1,len(word2)+1):
                if word1[i-1]==word2[j-1]:
                    dp[i][j]=dp[i-1][j-1]
                else:
                    #word1删去一个元素
                    c1=dp[i-1][j]+1
                    #word2删去一个元素
                    c2=dp[i][j-1]+1
                    #改变一个元素
                    c3=dp[i-1][j-1]+1
                    dp[i][j]=min(c1,c2,c3)
        return dp[-1][-1]

583.两个字符串的删除操作

思路：和编辑距离一样，就是条件少了一个。编辑距离是删除，增加，或者改变，这个题目只有删除。所以在代码里把“改变”的那个去掉就可以了。

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        dp=[[0 for i in range(len(word2)+1)] for _ in range(len(word1)+1)]
        #初始化
        for i in range(len(word2)+1):
            dp[0][i]=i 
        for i in range(len(word1)+1):
            dp[i][0]=i
        #两层循环
        for i in range(1,len(word1)+1):
            for j in range(1,len(word2)+1):
                if word1[i-1]==word2[j-1]:
                    dp[i][j]=dp[i-1][j-1]
                else:
                    #word1删去一个元素
                    c1=dp[i-1][j]+1
                    #word2删去一个元素
                    c2=dp[i][j-1]+1
                    dp[i][j]=min(c1,c2)
        return dp[-1][-1]

115.不同的子序列

代码随想录认准代码随想录，学习算法不迷路https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html#_115-%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]
        for i in range(len(s)):
            dp[i][0] = 1
        for j in range(1, len(t)):
            dp[0][j] = 0
        for i in range(1, len(s)+1):
            for j in range(1, len(t)+1):
                if s[i-1] == t[j-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[-1][-1]
1

力扣

最长公共子序列/子串

剑指offer-leetcode-最大最小问题-思路篇_MaYingColdPlay的博客-CSDN博客1.无重复字符最长子串双指针法，用一个left指针，指向最左边，一个cur指针，指向当前，记录两者之间的距离。用一个列表来记录当前无重复字符。如果有重复的子串，移动left指针。不用两个指针也可，直接用一个list来判断就行了。list+从左边pop出当前存在的。...https://blog.csdn.net/MaYingColdPlay/article/details/106035602

940. 不同的子序列 II

 力扣

重复的是前一个相同元素，之前的。不包含前一个相同的元素在内。

因为，前一个重复元素，本身这个值时可以包括在新增元素范围内的，两者重复的只有他之前的那些。

class Solution(object):
    def distinctSubseqII(self, s):
        """
        :type s: str
        :rtype: int
        """
        maps = collections.defaultdict(int)
        dp = [0 for _ in range(len(s)+1)]
        for i in range(1,len(s)+1):
            dp[i] = dp[i-1]*2 + 1
            if s[i-1] in maps:
                pre = maps[s[i-1]]
                dp[i] = dp[i] - pre - 1
            #重复的是前一个相同元素，之前的。不包含前一个相同的元素在内。
            maps[s[i-1]]=dp[i-1]
        return dp[-1] % (10**9+7)

1987. 不同的好子序列数目

#基本思路和940一样。dp[i]表示以i结尾的子序列的数量，从前往后找，dp[i]=2*dp[i-1]-dp[last]
#dp[i]=2*dp[i-1]-dp[last]。以s[i]结尾的子序列数量，是以s[i-1]结尾的子序列的数量+s[i-1]结尾的子序列的数量_尾部加上s[i]，再加上s[i]本身
#减去重复的，s[i]上一次出现之前的子序列的数量，再减去上一次出现的s[i]本身
#这个题只有1和0，分类讨论，记录上一次以1结尾的子序列的数量，和上一次以0结尾的子序列的数量。
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
        count1 = 0
        count0 = 0
        if_has0 = 0
        for i in range(len(binary)):
            if binary[i] == "1":
                count1 = count1 + count0 + 1
            if binary[i] == "0":
                count0 = count0 + count1
                if_has0 = 1
        return (count1+count0+if_has0)%(10**9+7)

2262. 字符串的总引力

 与940.不同的子序列2 思考方式类似，从左到右遍历，在前一个的末尾添加当前元素。

 

 

class Solution(object):
    def appealSum(self, s):
        """
        :type s: str
        :rtype: int
        """
        # dp[i]表示以i结尾的子字符串总引力
        dp = [0 for _ in range(len(s)+1)]
        maps = {}
        for i in range(1,len(s)+1):
            #s[i-1]结尾的字符串一共i个
            dp[i] = dp[i-1] + i
            if s[i-1] in maps:
                last = maps[s[i-1]]
                #s[start:i-1],当start在上一次出现元素之前时，都要去重
                dp[i] = dp[i]  - last
            maps[s[i-1]] = i
        return sum(dp)

828. 统计子串中的唯一字符

思路同940

力扣

力扣

class Solution(object):
    def uniqueLetterString(self, s):
        """
        :type s: str
        :rtype: int
        """
        #以s[i]结尾的子串的唯一字符，和以s[i-1]结尾的子串的唯一字符，的关系
        #如果s[i]之前没有出现过，以s[i-1]结尾的子串的唯一字符，都要加上1
        #如果s[i]之前出现过一次，出现的最后位置是j，s[j:i]之前加一
        #如果s[i]之前出现过大于等于2次，出现的最后位置是j1,j2，s[j:i]之前加一
        dp = [0 for _ in range(len(s)+1)]
        maps = collections.defaultdict(list)
        for i in range(1,len(s)+1):
            dp[i] = dp[i-1] + i 
            if s[i-1] in maps:
                last_list = maps[s[i-1]]
                if len(last_list) == 1:
                    dp[i] = dp[i] - 2*last_list[-1]
                else:
                    dp[i] = dp[i] - last_list[-1]-(last_list[-1] - last_list[-2])
            maps[s[i-1]].append(i)
        return sum(dp)

128. 最长连续序列

 set查询o(1)

521. 最长特殊序列 Ⅰ

脑筋急转弯

6107. 不同骰子序列的数目

记忆化深搜

class Solution:
    def distinctSequences(self, n: int) -> int:
        @lru_cache(None)
        def gcd(x, y):#寻找最大公约数
            if x % y == 0:
                return y
            return gcd(y, x % y)
        @lru_cache(None)
        def dfs(i, x, y):#分别是第几次掷骰子，上次点数，上上次点数
            if i == n - 1:#当最后一次掷骰子，就不需要继续向下深搜了，直接找到满足条件的点数数量即可
                res = 0
                for j in range(1, 7):
                    if j != x and j != y and gcd(x, j) == 1:#不能和上两次点数相同且与上一次点数最大公约数为1
                        res += 1
                return res
            res = 0
            for j in range(1, 7):
                if j != x and j != y and gcd(x, j) == 1:
                    res += dfs(i + 1, j, x)
                    res %= 10 ** 9 + 7
            return res
        return dfs(0, -1, -1)

作者：qin-qi-shu-hua-2
链接：https://leetcode.cn/problems/number-of-distinct-roll-sequences/solution/python-ji-yi-hua-shen-sou-by-qin-qi-shu-w070l/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2272. 最大波动的子字符串

 leetcode-记忆化深搜/动态规划v1_林冲风雪山神庙的博客-CSDN博客

6207. 统计定界子数组的数目

 枚举右端点

枚举右端点，同时用左端点保证内部没有出界的，然后从左端点到最远的最大值和最小值更近的那个的位置都可以作为开头

class Solution:
    def countSubarrays(self, nums: List[int], min_k: int, max_k: int) -> int:
        ans = 0
        min_i = max_i = i0 = -1
        for i, x in enumerate(nums):
            if x == min_k: min_i = i
            if x == max_k: max_i = i
            if not min_k <= x <= max_k: i0 = i  # 子数组不能包含 nums[i0]
            ans += max(min(min_i, max_i) - i0, 0)
            # 注：上面这行代码，改为手动算 min max 会更快
            # j = min_i if min_i < max_i else max_i
            # if j > i0: ans += j - i0
        return ans

作者：endlesscheng
链接：https://leetcode.cn/problems/count-subarrays-with-fixed-bounds/solution/jian-ji-xie-fa-pythonjavacgo-by-endlessc-gag2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。