面试题库 › 客户端 › 能量回复与技能释放的最大伤害 DP

能量回复与技能释放的最大伤害 DP

难度 ★★★在 1 场真实面经中被问到 方向:客户端考点:动态规划

哪些公司问过

快手1

常见岗位:游戏客户端

答案要点

  1. 状态 dp[t][e]:第 t 秒结束、能量为 e 时的最大累计伤害
  2. 转移:先放后回时新能量为 min(E, e-c_k+1);先回后放时先 min(E,e+1) 再扣 c_k
  3. 先确认回能与放技能的先后、初始能量,这决定转移细节和边界
  4. 复杂度 O(T·E),滚动数组空间 O(E);不可达状态初始化为负无穷
  5. T 远大于 E 时,用 (E+1) 维 max-plus 矩阵快速幂,复杂度 O(E³ log T)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题