题目

01-62-不同路径

01-62-不同路径

leetcode-62

• 输入：m*n 网格
• 目标：从左上角[0,0]，走到右下角[m-1,n-1]，一次只能走1步，只能向下或向右。
• 输出：到达终点，不同路径数量

DP网格不同路径数量

DP网格不同路径数量

• dp[i][j]：从[0,0]到[i,j]的不同路径数量

• 初始化：从[0,0]走到第0行或第0列，任意位置，路径都为1

• 递推公式：dp[i][j] = dp[i-1][j] + dp[i][j-1]

  $$\text{dp}[i][j]=\underset{\mathrm{从}\mathrm{上}\mathrm{面}\mathrm{过}\mathrm{来}}{\underbrace{\text{dp}[i-1][j]}}+\underset{\mathrm{从}\mathrm{左}\mathrm{边}\mathrm{过}\mathrm{来}}{\underbrace{\text{dp}[i][j-1]}}$$

def uniquePaths(self, m: int, n: int) -> int:
    """从[0,0]到[m-1,n-1]的不同路径总数量，只能向下或向右走，DP写法"""
    if m <= 0 or n <= 0:
        return 0

    # dp[i][j]: 从[0,0]走到[i,j]的不同路径数量
    dp = [[0]* n for _ in range(m)]

    # 初始化，第0行所有位置，都为1，第0列，所有位置路径都为1
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 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]

01-63-不同路径2

01-63-不同路径2

leetcode-63

• 输入：m*n 网格grid。有障碍物，0表示空，1表示障碍。
• 目标：从左上[0,0]走到右下[m-1,n-1]，只能向下或向右走。

DP起始路径有障碍物

DP起始路径有障碍物

• dp[i][j]：从00到ij的不同路径数量。
• 初始化
  • 00位置：无障碍 dp[0][0] = 1，否则为0
  • 第0行 第0列：有障碍物则不能到达。
• 递推公式
  • [i, j] 有障碍，dp[i][j] = 0
  • [i-1, j] 无障碍，dp[i][j] += dp[i-1][j]
  • [i, j-1] 无障碍，dp[i][j] += dp[i][j-1]

def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
    """带障碍物的路径数量，有障碍则不能过"""
    if not obstacleGrid or len(obstacleGrid) <= 0 or len(obstacleGrid[0]) <= 0:
        return 0

    m, n = len(obstacleGrid), len(obstacleGrid[0])

    # dp[i][j]：从00到ij的路径数量
    dp = [[0]*n for _ in range(m)]

    # 初始化00位置，无障碍才可达
    if obstacleGrid[0][0] == 0:
        dp[0][0] = 1
    else:
        return 0

    # 初始化第0行和第0列
    for i in range(1, m):
        if obstacleGrid[i][0]:
            # 有障碍，不可达
            dp[i][0] = 0
        else:
            # 无障碍，继承上1个位置数量
            dp[i][0] = dp[i-1][0]

    for j in range(1, n):
        if obstacleGrid[0][j]:
            # 有障碍，不可达
            dp[0][j] = 0
        else:
            # 无障碍，继承上一个位置数量
            dp[0][j] = dp[0][j-1]

    # 遍历递推计算其他位置
    for i in range(1, m):
        for j in range(1, n):
            if obstacleGrid[i][j]:
                dp[i][j] = 0
            else:
                # 从左或从上到达，无障碍才能到
                if obstacleGrid[i-1][j] == 0: 
                    dp[i][j] += dp[i-1][j]
                if obstacleGrid[i][j-1] == 0: 
                    dp[i][j] += dp[i][j-1]
    return dp[m-1][n-1]

02-64-最小路径和

02-64-最小路径和

leetcode-64

• 输入：m*n 网格，每个位置有1个数字
• 目标：从左上到右下，只能向下或向右走。
• 输出：找到一条路径，使得路径上的数字求和最小，返回最小路径和。

二维DP最小路径和

DP最小路径和

定义

• dp[i][j]：从00到ij的最小路径和。
• 初始化：dp[0][0], 第0行，第0列。

递推dp[i][j]

• 从左边来，从上边来，二者取其小

• dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

  $$\text{dp}[i][j]=min(\underset{\mathrm{从}\mathrm{上}\mathrm{面}\mathrm{过}\mathrm{来}}{\underbrace{\text{dp}[i-1][j]}},\underset{\mathrm{从}\mathrm{左}\mathrm{边}\mathrm{过}\mathrm{来}}{\underbrace{\text{dp}[i][j-1]}})+\text{grid}[i][j]$$

def minPathSum(self, grid: List[List[int]]) -> int:
    """给定m*n网格，每个位置代表数字，只能向下或向右走，从左上到右下，最小的路径和"""

    if not grid or not grid[0]:
        return 0

    m, n = len(grid), len(grid[0])
    # dp[i][j]：从00到ij的最小路径和
    dp = [[0]*n for _ in range(m)]

    # 初始化
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] += dp[i-1][0] + grid[i][0] 
    for j in range(1, n):
        dp[0][j] += dp[0][j-1] + grid[0][j] 

    # 遍历递推计算各位置
    for i in range(1, m):
        for j in range(1, n):
            # 递推，从左或上到达，取其小
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] 

    # 返回目的地的最小路径和
    return dp[m-1][n-1]

一维DP最小路径和

一维DP最小路径和

二维dp[i][j]：00到ij的最小路径。

$$\text{dp}[i][j]=min(\underset{\mathrm{从}\mathrm{上}\mathrm{面}\mathrm{过}\mathrm{来}}{\underbrace{\text{dp}[i-1][j]}},\underset{\mathrm{从}\mathrm{左}\mathrm{边}\mathrm{过}\mathrm{来}}{\underbrace{\text{dp}[i][j-1]}})+\text{grid}[i][j]$$

一维dp[j]：00到ij的最小路径。

• 省略i，每次遍历为第i行

  $$\text{dp}[j]=min(\underset{\mathrm{上}\mathrm{轮}\mathrm{上}\mathrm{面}}{\underbrace{\text{dp}[j]}},\underset{\mathrm{本}\mathrm{轮}\mathrm{左}\mathrm{边}}{\underbrace{\text{dp}[j-1]}})+\text{grid}[i][j]$$

• dp[j]：dp[i-1][j]，上一行的j，本行还未更新。

• dp[j-1]：dp[i][j-1]，当前行的j-1，本行已经更新

注意

• 初始化第0行、每行遍历初始化dp[0]

def minPathSum_1dp(self, grid: List[List[int]]) -> int:
    """给定m*n网格，每个位置代表数字，向下或向右走，左上到右下，最小路径和，1d写法，空间O(n)"""
    if not grid or not grid[0]:
        return 0

    m, n = len(grid), len(grid[0])

    # dp[i][j]，从00到ij的最小路径和
    # dp[j]，省略i，从00到ij的最小路径和，当前行，复用位置
    dp = [0] * n

    # 初始化第一行
    dp[0] = grid[0][0]
    for j in range(1, n):
        dp[j] = dp[j-1] + grid[0][j]  

    # 先行，再列，遍历递推各位置最小路径和
    for i in range(1, m):
        # [i,0]位置 没有初始化，这里需要初始化, dp[0]=dp[i-1][0]
        dp[0] = dp[0] + grid[i][0]  
        for j in range(1, n):
            # dp[j]=dp[i-1][j]，dp[j-1]=dp[i][j-1]
            # 从上来、左来，二者取其小
            dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
    return dp[n-1]

03-5-最长回文子串

03-5-最长回文子串

leertcode-5

• 输入：字符串s
• 输出：最长的回文子串

回文串中心扩展法

回文串中心扩展法

核心思想

• 回文串：关于中心对称。长度为奇数aba、长度为偶数abba。
• 遍历每个字符，以i为中心 向两侧扩展寻找回文子串
  • 奇数扩展：以i为中心
  • 偶数扩展：以i,i+1为中心
  • 谁大取谁：更新最长长度
• expand_around_center 函数：返回start, end, len

def longestPalindrome_center_expand(self, s: str) -> str:
    """最长回文子串，回文串是对称的，从中心扩展法"""
    if not s:
        return ""

    n = len(s)

    def expand_around_center(left, right):
        """从l, r出发，寻找最长回文串长度"""
        # 当指针在边界内，且左右字符相等时，继续往两边外
        while left >= 0 and right < len(s) and s[left] == s[right]:  
            left -= 1
            right += 1
        # 循环退出时，s[left] != s[right]，此时有效回文区间为 [left + 1, right - 1]
        # 长度公式为: (right - 1) - (left + 1) + 1 = right - left - 1
        start = left + 1
        end = right - 1
        return start, end, end-start+1

    start, end, max_len = 0, 0, 0

    for i in range(n):
        # 以i为中心，寻找奇数串长度
        odd_start, odd_end, odd_len = expand_around_center(i, i) 
        if odd_len > max_len:
            start, end, max_len = odd_start, odd_end, odd_len

        # 以i,i+1为中心，寻找偶数串长度
        even_start, even_end, even_len = expand_around_center(i, i+1) 

        # 奇数和偶数回文串，二者取其大
        if even_len > max_len:
            start, end, max_len = even_start, even_end, even_len

    return s[start:end+1]

DP 最长回文子串

DP最长回文子串

dp[i][j]定义

• dp[i][j]：子串s[i...j] 是否是 回文串。
• 初始化：dp[i][i] 单字符为回文串、相邻相同双字符为回文串。

递推公式

• s[i..j] 是回文串 --> s[i]==s[j]
• dp[i][j]=True ，如果s[i]==[sj] 且 ( j-i<=2 或 dp[i+1][j-1]=True)
• 遍历顺序：
  • 由于计算i依赖i+1，因此i从大到小遍历
  • 由于计算j依赖j-1、j>i，因此j从i+2开始 从小到大遍历

结果判断

• 遍历过程中，记录最长回文子串即可。

def longestPalindrome_dp(self, s: str) -> str:
    """dp查找最长回文子串"""
    if not s:
        return ""

    n = len(s)

    # dp[i][j]: 子串s[i..j]是否是回文串
    dp = [[False]* n for _ in range(n)]

    # 最长回文子串
    res = ""

    # 初始化，单字符为回文串
    for i in range(n):
        dp[i][i] = True
        # 记录长度为1的回文子串
        res = s[i]

    # 初始化，相邻相同双字符，为回文串
    for i in range(1, n):
        if s[i-1] == s[i]:
            dp[i-1][i] = True 
            # 记录长度为2的回文子串
            res = s[i-1:i+1]

    # 两层循环递推求解其余各值
    for i in range(n-2, -1, -1):  
        for j in range(i+2, n):  
            # 递推公式：dp[i][j]=True 如果s[i]=s[j] 且 (dp[i+1][j-1]=True 或 j-2<=2)
            if s[i] == s[j]:  
                # j>i，计算i, 依赖i+1， 遍历i时，需要逆序
                if j-i <= 2 or dp[i+1][j-1] == True:  
                    dp[i][j] = True
                    # 更新最长子串
                    if j-i+1 > len(res):
                        res = s[i:j+1]
    return res

Manacher回文串算法

马拉车回文串算法

新字符串生成 s->t

• 统一变成奇数长度字符串：每个字符前面加#，再首加^、尾加#$
• baba -> ^ #b#a#b#a# $
• bab -> ^ #b#a#b# $

p[i] 回文半径数组

• p[i]：以新字符串字符t[i]为中心，向外扩展最大回文半径。

最右回文center和right

• 最右回文区间

  • center：已知最右回文的中间点

  • right: 已知最右回文的右边界。

  • [center-p[center], center+p[center]]。[left ... center ... right]

  $$\underset{\mathrm{右}\mathrm{点}}{\underbrace{r}}=\underset{\mathrm{中}\mathrm{点}}{\underbrace{c}}+\underset{\mathrm{半}\mathrm{径}}{\underbrace{p[c]}}$$

• 为何是最右回文区间：从左至右遍历，关心右边有多少区域被当前回文覆盖。

依次遍历字符i判断

• 由于从左到右遍历，天然有：$left<center<i$

• $i<right$

  • i 在 [left, center, right] 大回文里

  • i有对称点：[left ... i_mirror ... center ... i ... right]

    $$i\mathrm{\_}mirror=2\ast center-i\leftarrow center-i\mathrm{\_}mirror=i-center$$

  • p[i] 初始值，保底半径

    • left..right是回文 --> i_mirror左右和i左右 相同

      $$p[i]=p[i\mathrm{\_}mirror]$$

    • 但p[i_mirror]可能超出左端点。只能保证 在[left right]内是回文，因此需取小

    $$p[i]=min(p[i\mathrm{\_}mirror],right-i)$$

  • 以i为中心继续向外扩展判断是否回文，循环p[i] += 1

• $i>right$

  • 未探测，使用中心扩展法(下文)，探测p[i]

• 更新最右边界

• 记录最长回文长度和中间点。

结果判断

• 计算最长回文起点：start=(max_center-max_len) // 2
• 在s中截取最长回文：s[start:start+max_len]

def longestPalindrome_manacher(self, s: str) -> str:
    """最长回文串，manacher 算法"""
    if not s or len(s) <= 1:
        return s

    # 1. 字符串预处理
    t = "^#" + "#".join(s) + "#$"
    n = len(t)

    # 2. p[i] 在t中以t[i]为中心，向外扩展的最大回文半径，半径不包含自身，应当初始化为0
    p = [0] * n

    # 3. 最右回文串中心点和右边点
    center = 0
    right = 0

    # 4. 全局最长回文串中心点和半径
    max_len = 0
    max_center = 0

    # 5. 依次遍历求解各个中心点
    for i in range(1, n-1):
        # 当前中心点，在当前最右回文串里，p[i]初始值继承p[mirror]
        if i < right:
            # l .. mirror .. center .. i .. right
            mirror = 2 * center - i
            # p[i] 初始值，取小，提防p[mirror]过大，超出left边界
            p[i] = min(p[mirror], right-i)

        # i中心继续向外扩张，p[i]半径+1
        while t[i+p[i]+1] == t[i-p[i]-1]:  
            p[i] += 1

        # 更新最右边界
        if i + p[i] > right:
            center = i
            right = i + p[i]

        # 更新全局最长回文串的半径和中间点
        if p[i] > max_len:
            max_len = p[i]  
            max_center = i 

    # 计算start, end
    start = (max_center - max_len) // 2
    end = start + max_len - 1
    return s[start:end+1]

04-1143-最长公共子序列

04-1143-最长公共子序列

leetcode-1143

• 输入：text1, text2
• 输出：最长公共子序列长度，如果没有返回-1

二维DP最长公共子序列

二维DP LCS

dp[i][j]定义

• dp[i][j]：text1前i个字符 和text2前j个字符 的最长公共子序列长度。
• dp数组大小： $(m+1)\times (n+1)$。
• 初始化：第0行第0列全部为0，即空字符串。

dp[i][j]递推公式

• 字符 i==j

  $$\text{dp}[i][j]=\text{dp}[i-1][j-1]+1$$

• 字符 i!=j，丢弃i或丢弃j，取最长公共子序列

  $$\text{dp}[i][j]=max(\text{dp}[i-1][j],\text{dp}[i][j-1])$$

最终结果

• dp[m][n]

def longestCommonSubsequence_2dp(self, text1: str, text2: str) -> int:
    """最长公共子序列，二维DP"""
    if not text1 or not text2:
        return 0

    m, n = len(text1), len(text2)

    # dp[i][j]：text1前i个字符和text2前j个字符的公共子序列长度
    dp = [[0]*(n+1) for _ in range(m+1)] 

    # 初始化，第0行、第0列，均为0，空字符串嘛

    # 递推计算其余各位置长度
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[j-1]:
                # 末尾对上了，长度+1
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                # 尾串没对上，尝试各丢1个，选择长度大的
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
    # 返回结果
    return dp[m][n]

一维DP最长公共子序列

一维DP最长公共子序列

dp[j]定义

• dp[j]：隐藏i，当前i, text1 前i个字符 和text2 前j个字符，最长公共子序列长度。

一维DP 遍历j时三个关键状态

• prev：$\text{dp}[i-1][j-1]$，上一轮，上一行左上角
• $\text{dp}[j]$：$\text{dp}[i-1][j]$，上一轮，上一行同列
• $dp[j-1]$：$\text{dp}[i][j-1]$，当前轮，当前行左边

递推公式

• 若字符 i==j

  • 二维dp
  $$\text{dp}[i][j]=\text{dp}[i-1][j-1]+1$$
  • 一维dp：$\text{dp}[i-1][j-1]$ 需用 prev 保存：

$$\text{dp}[j]=\text{prev}+1$$

• 若字符 i!=j

  • 二维dp
  $$dp[i][j]=max(\text{dp}[i-1][j],\text{dp}[i][j-1])$$
  • 一维DP
  $$dp[j]=max(\text{dp}[j],\text{dp}[j-1])$$

注意

• 一维dp：依赖左上角 $\text{dp}[i-1][j-1]$时，需提前存储temp，每次更新。
• 每行开始，prev=dp[i-1][0]=0

更新顺序

temp = dp[j]  # 保存 dp[i-1][j]

if text1[i - 1] == text2[j - 1]:
  dp[j] = prev + 1
else:
  dp[j] = max(dp[j], dp[j - 1])
  
prev = temp  # 本轮的 dp[i-1][j]，成为下一个 j 的 dp[i-1][j-1]

完整代码

def longestCommonSubsequence_1dp(self, text1: str, text2: str) -> int:
    """最长公共子序列，1维dp写法"""
    if not text1 or not text2:
        return 0

    m, n = len(text1), len(text2)
    # dp[j]：text1前i和text2前j的最长公共子序列长度
    dp = [0] * (n+1)
    # 遍历递推计算
    for i in range(1, m+1):
        # 用作记录 dp[i-1][j-1] 
        prev = 0
        for j in range(1, n+1):
            # 暂存 dp[j]=dp[i-1][j]
            temp = dp[j]  
            if text1[i-1] == text2[j-1]:
                # prev为dp[i-1][j-1]，非常重要
                dp[j] = prev + 1
            else:
                # 上侧，上轮dp[i-1][j], 左侧，本轮dp[i][j-1] 
                dp[j] = max(dp[j], dp[j-1])

            # j下一次遍历时，作为即dp[i-1][j-1]，左上角
            prev = temp  
    return dp[n]

05-72-编辑距离

05-72-编辑距离

leetcode-72

• 输入：word1、word2
• 输出：把word1转为word2的最少操作数
• 操作：插入字符、删除字符、替换字符

二维DP编辑距离

二维DP编辑距离

dp[i][j]定义

• dp[i][j]：把word1前i个字符，变成word2前j个字符，所需的最少编辑次数。
• dp尺寸：$(m+1)\times (n+1)$

初始化

• 初始化第0行 dp[0][j]=j，w1为空，变成w2，一直追加。
• 初始化第0列 dp[i][0]=i，w1有值，w2为空，w1变w2。一直删除。
• 最终结果：dp[m][n]

dp[i][j] 前i变前j次数 递推公式

• 字符i==j：纯 前i-1变前j-1次数

  $$dp[i][j]=dp[i-1][j-1]$$

• 字符i!=j，有3种情况，取其小

  • 替换i为j字符：前i-1变前j-1次数 + 1

    $$dp[i][j]=dp[i-1][j-1]+1$$

  • 删除i字符：前i-1变前j次数 + 1

    $$dp[i][j]=dp[i-1][j]+1$$

  • i后插入j字符：前i变前j-1次数 + 1

    $$dp[i][j]=dp[i][j-1]+1$$

  • 三种变换取最小

    $$\text{dp}[i][j]=min(\underset{i\mathrm{替}\mathrm{换}\mathrm{为}j}{\underbrace{\text{dp}[i-1][j-1]}},\underset{\mathrm{删}\mathrm{除}i}{\underbrace{\text{dp}[i-1][j]}},\underset{i\mathrm{后}\mathrm{插}\mathrm{入}j}{\underbrace{\text{dp}[i][j-1]}})+1$$$$\text{dp}[i][j]=min(\text{dp}[i-1][j-1],\text{dp}[i-1][j],\text{dp}[i][j-1])+1$$

def minDistance_2dp(self, word1: str, word2: str) -> int:
    """word1变word2的最小编辑距离，2维dp写法"""

    m, n = len(word1), len(word2)

    # dp[i][j] 前i字符变前j字符，最小编辑距离
    dp = [[0]*(n+1) for _ in range(m+1)]

    # 初始化第0行，w1为空，变成w2
    for j in range(1, n+1):
        # w1 前0个字符，变成w2 前j个字符，所需最小编辑距离，全部增加
        dp[0][j] = j

    # 初始化第0列，w1有值，w2为空，w1变w2
    for i in range(1, m+1):
        # w1 前i个字符，变成w2 前0个字符，所需最小编辑距离，全部删除
        dp[i][0] = i

    # 递推计算其余各位置值
    for i in range(1, m+1):
        for j in range(1, n+1):
            if word1[i-1] == word2[j-1]:
                # 字符i==j
                dp[i][j] = dp[i-1][j-1]
            else:
                # 字符i!=j，替换i、删除i、i后面追加新字符，三种情况，取最小编辑距离
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
    return dp[m][n]

一维DP编辑距离

一维DP编辑距离

dp[j]定义

• 当前i, word1前i个字符变成word2前j个字符，最短编辑距离

初始化

• 第0行 i=0，w1为空，w2有值，i=0 变成各j 所需最短距离。

遍历j时3个状态

• prev：$\text{dp}[i-1][j-1]$，上一轮，上一行左上角
• $\text{dp}[j]$：$\text{dp}[i-1][j]$，上一轮，上一行同列
• $dp[j-1]$：$\text{dp}[i][j-1]$，当前轮，当前行左边

1维dp递推公式

• 字符 i==j

  $$dp[i][j]=dp[i-1][j-1]+1$$$$dp[j]=prev+1$$

• 字符 i!=j

  $$\text{dp}[i][j]=min(\underset{i\mathrm{替}\mathrm{换}\mathrm{为}j}{\underbrace{\text{dp}[i-1][j-1]}},\underset{\mathrm{删}\mathrm{除}i}{\underbrace{\text{dp}[i-1][j]}},\underset{i\mathrm{后}\mathrm{插}\mathrm{入}j}{\underbrace{\text{dp}[i][j-1]}})+1$$$$\text{dp}[j]=min(\text{prev},\text{dp}[j],\text{dp}[j-1])+1$$

注意

• 一维dp：依赖左上角 $\text{dp}[i-1][j-1]$时，需提前存储temp，每次更新。
• 每行开始：prev=dp[i-1][0]=dp[0] ，当前轮 dp[0]=i

def minDistance_1dp(self, word1: str, word2: str) -> int:
    """word1变word2的最小编辑距离，1维dp写法"""
    m, n = len(word1), len(word2)
    # dp[j]：当前i，w1前i个字符，变成w2前j个字符，所需的最短编辑距离
    dp = [0] * (n+1)
    # 初始化第0行，i=0时的内容，变成w2各j字符，所需距离
    for j in range(1, n+1):
        dp[j] = j

    for i in range(1, m+1):
        # 遍历j时，依赖dp[i-1][j-1]，
        # 获取上一轮dp[0], prev为上一轮dp[i-1][0]，即dp[0], j=1时需要
        prev = dp[0]  
        # 更新当前轮, dp[i][0] 为i，全部删除, 前i字符，变成前j=0字符，所需次数
        dp[0] = i  
        for j in range(1, n+1):
            # temp=dp[i-1][j]
            temp = dp[j]
            if word1[i-1] == word2[j-1]:
                # dp[i][j] = dp[i-1][j-1]
                dp[j] = prev
            else:
                # dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) +1
                dp[j] = min(prev, dp[j], dp[j-1]) + 1
            prev = temp  

    return dp[n]