重练算法（代码随想录版） day45 - 动态规划part12

今日刷题量：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/