LeetCode 刷题 01

动态规划（Dynamic Programming，DP）是一种通过将复杂问题分解为重叠子问题，并存储子问题的解以避免重复计算，从而高效求解最优化问题的方法。其核心思想包括：

1. 最优子结构：问题的最优解包含子问题的最优解。
2. 重叠子问题：子问题在求解过程中被多次重复计算。
3. 状态转移方程：定义如何从子问题的解推导出原问题的解。
4. 记忆化存储：通常用数组或哈希表保存已计算的子问题结果。

常见应用包括最短路径、背包问题、序列对齐等。

二维动态规划类题目的标配是一个二维矩阵。我们一般从边缘开始入手，先处理位置 (0, 0) 的情况，再同时处理第 0 行和第 0 列的情况。

点 (i, j) 的状态一般取决于 (i-1, j)、(i, j-1)、(i-1, j-1) 三个位置的值。重点是需要弄明白这些点之间状态的转移是如何进行的。

二维动态规划的解题流程可以概括为以下几步：

graph LR
  A["① 定义状态 dp[i][j]"] --> B["② 初始化边界"]
  B --> C["③ 推导转移方程"]
  C --> D["④ 确定遍历顺序"]

给定一个包含非负整数的 m × n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或向右移动一步。

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    
    # 初始化第 0 行
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    
    # 初始化第 0 列
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    
    # 状态转移
    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]
  

一个机器人位于一个 m × n 网格的左上角，机器人每次只能向下或向右移动一步。机器人试图达到网格的右下角，问总共有多少条不同的路径。

这道题也有数学解法：从 (0, 0) 到 (m-1, n-1) 共需走 m+n-2 步，其中选 m-1 步向下，因此答案为 $C_{m+n-2}^{m-1}$。

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

重点在于不改变顺序。由于要求两者都按顺序取字母，可以减小问题规模：对于 text1 的前 i 个字母与 text2 的前 j 个字母：

• 若 text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
• 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

要找到最长回文子串，从一个点出发向两边延伸，看能延伸到多长。对于回文子串类问题，有两种情况：奇数长度回文子串和偶数长度回文子串。

对于一个回文子串，我们可以减小问题规模：去掉两端的字符后，如果它仍然是回文子串，那么原来的串也是。定义 dp[i][j] 表示 s[i..j] 是否为回文串：

注意遍历顺序：需要按子串长度从小到大遍历。

背包问题同样是二维 DP 的经典应用。将一个数字表示成幂的和的方案数（LC 2787）就是一个变体：

class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        MOD = 10**9 + 7
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(1, n + 1):
            val = i ** x
            for j in range(n + 1):
                dp[i][j] = dp[i - 1][j]
                if j >= val:
                    dp[i][j] = (dp[i][j] + dp[i - 1][j - val]) % MOD
        return dp[n][n]
  

这里 dp[i][j] 表示用前 i 个数字凑出和为 j 的方案数。对于每个数字，有选或不选两种决策，这正是 0-1 背包的标准模板。