今日刷题量：3
当前刷题总量：166
Easy: 62
Mid: 94
Hard: 10
Day45
解题思想
三道题都是字符串动态规划问题
- 都涉及两个字符串的前缀子问题
- 都可以用二维 DP 表表示 dp[i][j]
- DP 思路核心：
- 定义 dp[i][j] 表示 前 i 个字符与前 j 个字符的某种关系
- 状态转移由 当前字符是否匹配 或 可选操作 决定
115：目标：统计方法数 → 计数型 DP
- 核心：当前字符匹配可以选择用或不用 → dp[i][j] = dp[i-1][j] (+ dp[i-1][j-1] if match)
- 空间优化：一维数组 + 倒序遍历
583：目标：求最少删除次数 → 可转化为 LCS 问题
- 核心：找到 LCS → 删除不在 LCS 的字符
- 公式：minDelete = (len1 - LCS) + (len2 - LCS)
- 优化：可以用一维数组保存上一行 LCS
72：目标：求最少操作次数 → 通用型 DP
- 核心：考虑三种操作（插入、删除、替换）
- 状态转移：
- dp[i][j] = if same → dp[i-1][j-1]
else → min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1) - 优化：一维 DP + 变量保存左上角值
练习题目
115.不同的子序列（hard）：https://leetcode.cn/problems/distinct-subsequences/description/
583. 两个字符串的删除操作（mid）：https://leetcode.cn/problems/delete-operation-for-two-strings/description/
72. 编辑距离（mid）：https://leetcode.cn/problems/edit-distance/description/