【力扣hot100】刷题笔记Day26

前言

• 这几天终于要开始学多模态 / 大模型了，甚至想同时参加Agent比赛？but刷题依然不能落下，救命，分身乏术啊啊啊

62. 不同路径 - 力扣（LeetCode）

• 动态规划

  • class Solution:
        def uniquePaths(self, m: int, n: int) -> int:
            dp = [[1] * n for _ in range(m)]  # dp[i][j]表示到达i+1行j+1列的路径数，初始化为1
            for i in range(1, m):
                for j in range(1, n):
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]  # 到达上面的路径数 + 到达左边的路径数
            return dp[m-1][n-1]  # 到达右下角的路径数
    

64. 最小路径和 - 力扣（LeetCode）

• 动态规划

  • class Solution:
        def minPathSum(self, grid: List[List[int]]) -> int:
            m, n = len(grid), len(grid[0])
            dp = grid[:]  # 直接复制grid作为二维dp数组，dp[i][j]表示到达grid[i][j]最小数字总和
            for i in range(1, m): dp[i][0] += dp[i-1][0]  # 列初始化为前缀和
            for j in range(1, n): dp[0][j] += dp[0][j-1]  # 行初始化为前缀和
            for i in range(1, m):
                for j in range(1, n):
                    # 当前最小数字总和 =（上面的最小数字总和+当前值，左边的最下数字总和+当前值）的最小值
                    dp[i][j] = min(dp[i-1][j] + grid[i][j], dp[i][j-1] + grid[i][j])
            return dp[m-1][n-1]  # 返回右下角
    

5. 最长回文子串 - 力扣（LeetCode）

• 动态规划

  • class Solution:
        def longestPalindrome(self, s: str) -> str:
            n = len(s)
            dp = [[False] * n for _ in range(n)]  # dp[i][j]表示s[i,j]是否是回文子串
            max_len = 0
            res = ''
            for i in range(n-1, -1, -1):  # 从下到上
                for j in range(i, n):  # 从左到右
                    if s[i] == s[j]:
                        if j - i <= 1:  # 1个或2个是回文串
                            dp[i][j] = True
                            if j - i + 1> max_len:     # 更新最长回文子串
                                max_len = j - i + 1
                                res = s[i:j+1]
                        elif dp[i+1][j-1]:   # 前一个是回文串
                            dp[i][j] = True            
                            if j - i + 1> max_len:     # 更新最长回文子串
                                max_len = j - i + 1
                                res = s[i:j+1]
            return res
    

1143. 最长公共子序列 - 力扣（LeetCode）

• 动态规划（二维）

  • 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)]   # dp[i][j]表示text1[0,i-1]和text2[0,j-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-1][j], dp[i][j-1])
            return dp[m][n]
    

• 动态规划（一维）

  • class Solution:
        def longestCommonSubsequence(self, text1: str, text2: str) -> int:
            m, n = len(text1), len(text2)
            dp = [0] * (n+1)
            for i in range(1, m+1):
                pre = 0
                for j in range(1, n+1):
                    cur = dp[j]  # cur记录未覆盖的dp[i-1][j-1]，左上角的值
                    if text1[i-1] == text2[j-1]:    # 相等的话一起回退一格
                        dp[j] = pre + 1  # pre相当于dp[i-1][j-1]，左上角的值
                    else:  # 不相等就取各自回退一格的子序列的最大
                        dp[j] = max(dp[j], dp[j-1])
                    pre = cur    # 更新pre
            return dp[n]
    

 72. 编辑距离 - 力扣（LeetCode）

• 动态规划

  • class Solution:
        def minDistance(self, word1: str, word2: str) -> int:
            m, n = len(word1), len(word2)
            dp = [[0] * (n+1) for _ in range(m+1)]  # dp[i][j]表示word1[0,i-1]转换为word[0,j-1]的最少操作次数
            for i in range(m+1): dp[i][0] = i  # word1[0,i-1]变成空字符串，删除i次
            for j in range(n+1): dp[0][j] = j  # word2[0,j-1]变成空字符串，删除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-1][j-1]+1
                        # 删除（包含增加）：dp[i-1][j]+1  dp[i][j-1]+1
                        dp[i][j] = min(dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1)
            return dp[m][n]
    

后言

• 代码随想录的动态规划题好多，刷了得有三四天了，另外还被导师催干活催麻了，舍友都要面上实习了，我也想赶紧去工作呜呜呜，赶紧刷完题收拾收拾简历开始投了，不然金三银四就无了，时不我待啊啊啊