2370. 最长理想子序列（Rating 1834）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

2370. 最长理想子序列

Rating 1834

思路

套路1: 看到子序列和相邻就可以往动态规划上想

套路2：当字符串只含有小写字母，就可以考虑通过遍历26个字母的思路来求解。

设dp[i][j]表示[0, i]范围以字母j为结尾的最长理想子序列，动态规划

代码

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        n = len(s)
        dp = [[0 for _ in range(26)] for _ in range(n)] # 初始化
        dp[0][ord(s[0]) - ord('a')] = 1 # 初始化
        for i in range(1, n):
            for j in range(26): # 遍历26个字母
                dp[i][j] = dp[i - 1][j]
            j = ord(s[i]) - ord('a') # 对于当前字母
            for x in range(k + 1): # 遍历差距在k以内的字母
                dp[i][j] = max(dp[i][j], 1 + dp[i - 1][min(j + x, 25)], 1 + dp[i - 1][max(j - x, 0)])
        return max(dp[-1])