面试算法题：给定移动速度，求最大可捕获宝可梦数量

核心思路 #

这个问题本质是带时间约束的路径选择问题，贪心策略容易错过后续更优组合，暴力枚举所有子集的时间复杂度为O(2^M)完全不可行，正确解法是排序+动态规划。

具体步骤 #

1. 排序宝可梦
   把所有宝可梦按出现时间t_i从小到大排序。因为时间单向流动，不可能先捕获晚出现的宝可梦再回头抓早出现的，排序后可按时间顺序依次处理每只宝可梦。

2. 动态规划设计

   • 定义dp[i]：表示最后捕获第i只宝可梦时，能抓到的最大数量。
   • 初始化：对每只宝可梦i，计算从初始位置P到pos_i的移动时间move_time = |pos_i - P| / X，如果move_time <= t_i（能赶在它出现时或之前到达），则dp[i] = 1，否则dp[i] = 0（这只宝可梦无法捕获）。
   • 状态转移：对每只宝可梦i，遍历所有时间更早的宝可梦j（j < i），计算从pos_j到pos_i的移动时间time_needed = |pos_i - pos_j| / X，如果t_j + time_needed <= t_i（抓完j后能赶在i出现时到达），就更新dp[i] = max(dp[i], dp[j] + 1)。

3. 计算结果
   遍历整个dp数组，取最大值就是最多能捕获的宝可梦数量。

示例验证 #

举个简单例子：

• 初始位置P=7，移动速度X=1栋/秒
• 宝可梦列表：
  • A：t=1，pos=7
  • B：t=6，pos=5

排序后顺序是A、B：

• 初始化：dp[A] = 1（从7到7耗时0≤1），dp[B] =1（从7到5耗时2≤6）
• 状态转移：检查A到B，1+2=3≤6，所以dp[B] = max(1, 1+1)=2
• 最终结果是2，符合预期。

为什么贪心不行？ #

贪心策略比如“先抓最早出现的”或“先抓离当前位置最近的”都可能失效。比如：

• 初始位置P=1，X=1
• 宝可梦X：t=5，pos=6（移动耗时5，刚好赶在出现时到达）
• 宝可梦Y：t=3，pos=3（移动耗时2，能抓）
• 宝可梦Z：t=6，pos=7（从X出发移动耗时1，到达时间5+1=6；从Y出发移动耗时4，到达时间3+4=7>6，抓不到）

如果贪心先抓Y，最后只能抓1只；但直接抓X再抓Z，能抓2只，明显更优。这说明贪心会因为眼前的小选择阻断后续更多的捕获机会。

复杂度分析 #

• 时间复杂度：O(M²)，其中M是宝可梦数量。排序耗时O(M log M)，DP状态转移是O(M²)，面试场景下M通常不会太大（比如≤1000），这个复杂度完全能接受。
• 空间复杂度：O(M)，只需要存储DP数组。

内容的提问来源于stack exchange，提问作者Maggi Iggam