[动态规划 滑动窗口]
1. 定义DP状态（核心思路）
问题分析：
将 word1 转换为 word2，每个操作对应状态转移。定义 dp[i][j] 表示将 word1[0..i-1] 转换为 word2[0..j-1] 的最小操作数。
2. 初始化DP表
目的：处理空字符串的边界情况。
3. 填充DP表（状态转移方程）
状态转移逻辑：
- 若
word1[i-1] == word2[j-1]：无需操作，直接继承左上方值 →dp[i][j] = dp[i-1][j-1] - 否则：取三种操作的最小值 + 1
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 定义 dp[i][j] 表示将 word1[0..i-1] 转换为 word2[0..j-1] 的最小操作数。
for (int i = 0; i <= m; ++i) dp[i][0] = i;
for (int j = 0; j <= n; ++j) dp[0][j] = j;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min({dp[i - 1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
}
}
}
return dp[m][n];
}
};关键点解析
-
时间复杂度与空间复杂度
- 时间复杂度：O(mn)（双重循环）
- 空间复杂度：O(mn)（二维DP表）
-
状态转移方程的理解
- 删除操作：
dp[i-1][j]→ 删除word1的第i个字符后，匹配到word2的前j个字符 - 插入操作：
dp[i][j-1]→ 插入word2的第j个字符后，匹配到word2的前j个字符 - 替换操作：
dp[i-1][j-1]→ 将word1的第i个字符替换为word2的第j个字符
- 删除操作：
1. 处理特殊情况
目的：处理空字符串或无效输入，直接返回空结果。
2. 初始化字符计数器
目的：统计目标字符串 t 的字符需求，并为滑动窗口建立字符统计。
实现步骤：
- 使用哈希表（或数组）记录
t中每个字符的出现次数。 - 定义窗口哈希表，动态记录当前窗口内字符的出现次数。
- 初始化有效计数
valid，用于判断窗口是否覆盖t的所有字符。
3. 滑动窗口主体框架
目的：用双指针维护窗口，右指针扩展窗口，左指针收缩窗口。
实现步骤：
- 定义左右指针
left=0, right=0，初始化最小窗口长度和起始位置。 - 右指针遍历字符串，更新窗口统计。
- 当窗口满足覆盖条件时，收缩左指针寻找最小窗口。
4. 右指针扩展逻辑
目的：更新窗口字符计数，并检查是否满足 t 的需求。
关键点：
- 仅处理
t中需要的字符。 - 当窗口内某字符数量达到
t的需求时，valid自增。
5. 判断窗口覆盖条件
目的：当 valid 等于 need 的字符种类数时，说明窗口已覆盖 t。
6. 左指针收缩逻辑
目的：收缩窗口左边界，尝试找到更小的覆盖子串。
关键点：
- 左移时需检查移出的字符是否影响
valid。 - 更新窗口统计时需反向操作（与右指针扩展相反）。
class Solution {
public:
string minWindow(string s, string t) {
if (s.empty() || t.empty() || s.length() < t.length()) return "";
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int valid = 0;
int left = 0, right = 0;
int start = 0, min_len = INT_MAX;
while (right < s.size()) {
// 右指针扩展
char c = s[right++];
if (need.count(c)) {
window[c]++;
if (window[c] == need[c]) {
valid++;
}
}
while (valid == need.size()){
if (right - left < min_len) {
min_len = right - left;
start = left;
}
char d = s[left++];
if (need.count(d)) {
if (window[d] == need[d]) {
valid--;
}
window[d]--;
}
}
}
return min_len == INT_MAX ? "" : s.substr(start, min_len);
}
};1. 处理特殊情况
目的：处理金额为0或硬币数组为空的情况，直接返回结果。
2. 初始化动态规划数组
目的：定义 dp[i] 表示凑成金额 i 所需的最少硬币数，初始化为不可达值（amount + 1），并将 dp[0] 设为0。
3. 状态转移填充
目的：遍历每个硬币面额，更新所有可能金额的最小硬币数。
实现步骤：
- 外层循环遍历每个硬币面额。
- 内层循环从当前硬币面额开始，到目标金额
amount结束，更新dp[j]。
状态转移方程：
dp[j] = min(dp[j], dp[j - coin] + 1)
表示使用当前硬币coin时，金额j的最优解可能来自j - coin的解加1
4. 处理结果
目的：判断最终结果是否有效，返回最少硬币数或 -1。
解释：
- 若
dp[amount]仍为初始值amount + 1，说明无法兑换，返回-1
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) return 0;
if (coins.empty()) return -1;
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int coin : coins) {
for (int j = coin; j <= amount; ++j) {
dp[j] = min(dp[j], dp[j - coin] + 1);
}
}
return (dp[amount] > amount)?-1:dp[amount];
}
};