Day 22。
今天两道题分别是 Wildcard Matching 和 Jump Game II。
一道是 动态规划匹配题，一道是 经典贪心跳跃题。

今天的关键词：动态规划、状态转移、通配符匹配、贪心、覆盖范围、最少步数。

🧠 LeetCode 44 – Wildcard Matching

💡 思路总结

这题要求判断字符串 s 和模式串 p 是否匹配。
其中模式串里有两个特殊字符：

  • ?：匹配任意单个字符
  • *：匹配任意长度字符串（包括空串）

这题和普通字符串匹配不一样，因为 * 会带来很多可能性。
所以这题非常适合用：

动态规划

你的思路就是标准 DP 写法：

  • dp[i][j] 表示：
    • s 的前 i 个字符
    • 是否能和 p 的前 j 个字符匹配

这个定义非常关键，一旦状态定义清楚，后面的转移就顺了。

💻 代码实现

class Solution {
public:
    bool isMatch(string s, string p) {
        int n1 = s.size(),n2 = p.size();
        vector<vector<bool>> dp(n1+1,vector<bool> (n2+1,false));
        //空字符串匹配
        dp[0][0] = true;
        for(int j = 1;j<=n2;j++){
            if(p[j-1]=='*')dp[0][j]=dp[0][j-1];
        }

        for(int i = 1;i<=n1;i++){
            for(int j = 1;j<= n2;j++){
                if(s[i-1]==p[j-1] || p[j-1]=='?')dp[i][j]=dp[i-1][j-1];
                else if(p[j-1] == '*')dp[i][j] = dp[i][j-1] || dp[i-1][j];
            }
        }
        return dp[n1][n2];
    }
};

📌 知识点总结

1️⃣ 状态定义是这题的核心

这题最重要的第一步就是想清楚：

dp[i][j] = s 的前 i 个字符，和 p 的前 j 个字符是否匹配

只要这个状态定义立住了，后面就只是在分类讨论当前字符怎么转移。

2️⃣ 空串初始化很关键

你这里写了：

dp[0][0] = true;

这表示：

  • 空串和空模式串当然可以匹配

然后又处理了：

for(int j = 1; j <= n2; j++){
    if(p[j-1] == '*') dp[0][j] = dp[0][j-1];
}

这一步特别重要。
因为只有连续的 * 才能匹配空串。

比如：

  • "" 和 "*" 能匹配
  • "" 和 "**" 也能匹配
  • "" 和 "*a" 就不能匹配

3️⃣ 普通字符和 ? 的转移

如果当前字符满足：

s[i-1] == p[j-1] || p[j-1] == '?'

那说明这两个位置可以直接配对，转移就是：

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

意思很直观：

当前这一个字符匹配上了，那就看前面的部分能不能匹配。

4️⃣ * 的转移最关键

这一句是灵魂：

dp[i][j] = dp[i][j-1] || dp[i-1][j];

要理解透。

情况一：dp[i][j-1]

表示：

  • * 匹配空串

也就是模式串当前这个 * 不干活，直接看前面能不能匹配。

情况二：dp[i-1][j]

表示：

  • * 匹配至少一个字符

也就是 * 把 s[i-1] 吃掉了，然后继续留在原地，后面还能继续匹配更多字符。

这就是这题最关键的状态转移思想。

5️⃣ 这是典型的“匹配型 DP”

这类题经常有类似特征：

  • 两个字符串
  • 一个主串，一个模式串
  • 问能不能匹配
  • 有特殊符号 / 特殊规则

遇到这种题，就很适合往 DP 上想。

🦘 LeetCode 45 – Jump Game II

💡 思路总结

这题要求用最少的跳跃次数到达数组最后一个位置。
每个位置 i 的值 nums[i] 表示你从这里最多可以跳多远。

这题如果暴力想：

  • 每次尝试所有跳法
  • 找最少步数

会很慢。
而这题最经典的做法其实是：

贪心

你的思路非常标准：

  • currEnd：当前这一步最远能覆盖到哪里
  • maxEnd：在当前覆盖范围内，下一步最远能到哪里
  • 当遍历到 currEnd 时，说明当前这一步走完了，必须跳一次

💻 代码实现

class Solution {
public:
    int jump(vector<int>& nums) {
        int step=0;
        int currEnd = 0;
        int maxEnd = 0;
        for(int i = 0;i<nums.size()-1;i++){
            maxEnd = max(maxEnd,i+nums[i]);
            if(i == currEnd){
                step++;
                currEnd = maxEnd;
            }
        }
        return step;
    }
};

📌 知识点总结

1️⃣ 这题不是问“能不能到”，而是问“最少几步”

和 Jump Game I 不一样，这题要求的是最少跳跃次数。
所以重点不只是覆盖，而是：

每一步都尽量把下一步可达范围扩到最远

这就是贪心的味道。

2️⃣ currEnd 和 maxEnd 要分清

这两个变量是整题核心。

currEnd

表示：

当前已经用了 step 步，最远能到哪里

maxEnd

表示：

在当前这一步覆盖范围内，再多看一层，下一步最远能到哪里

所以遍历过程中不断更新：

maxEnd = max(maxEnd, i + nums[i]);

其实是在统计“下一步潜力最大能跳到哪里”。

3️⃣ 为什么 i == currEnd 时要加一步

当遍历到：

i == currEnd

说明你已经把当前这一步能覆盖的所有位置都看完了。
这时候必须真的“跳”一次，进入下一层范围：

step++;
currEnd = maxEnd;

这个过程特别像 BFS 分层：

  • 当前层所有位置都看完
  • 层数加一
  • 进入下一层

所以这题虽然写法像贪心，理解上也可以带一点“层次遍历”的感觉。

4️⃣ 为什么循环只到 nums.size() - 2

你这里写的是：

for(int i = 0; i < nums.size() - 1; i++)

这是对的。
因为最后一个位置不需要再往后跳了，所以没必要继续处理它。

5️⃣ 这是非常经典的贪心题

这题很值得记住，因为它不是那种“看起来就很贪心”的题，而是需要你观察出：

每一步不需要真的决定跳到哪个点，只需要维护这一层最远覆盖范围。

这是很漂亮的思维转换。

🧩 今日总结

题目核心思想
LeetCode 44动态规划 + 通配符匹配 + 状态转移
LeetCode 45贪心 + 覆盖范围维护 + 最少跳跃

今天两题风格差异挺大：

  • 44 偏 DP 和字符串匹配
  • 45 偏贪心和区间覆盖

但它们都在训练一件事：

把题目抽象成状态或者范围，然后再去推答案。

🧠 今日收获

今天最值得记住的两个模型：

1. 字符串匹配型 DP

如果题目里有：

  • 两个字符串
  • 特殊匹配规则
  • 问能否匹配

那就优先想：

  • dp[i][j] 的定义
  • 当前字符怎么转移
  • 初始化怎么处理

2. 区间覆盖型贪心

如果题目本质上是在问：

  • 当前一步能覆盖哪里
  • 下一步最远能扩到哪里
  • 最少要扩几次

那就很可能是：

  • 贪心
  • 区间扩展
  • 分层推进

💬 写给自己的话

Day 22 了。

你现在已经开始稳定接触这些不同流派的经典题了：

  • DP
  • 贪心
  • 回溯
  • 双指针
  • 二分
  • 栈

这说明你的刷题体系正在一点一点变完整。

别急着求“全都会”，
先把这些经典模型一块一块啃下来。
等这些模块逐渐熟悉之后，你会发现很多新题其实都只是它们的变形。

继续坚持。
Day 22，不只是数字在增加，你的题感和模型库也在一起增长。

阿玉，Day 22，继续冲。

—— 刷题第 22 天