能量回复与技能释放的最大伤害 DP
哪些公司问过
答案要点
- 状态 dp[t][e]:第 t 秒结束、能量为 e 时的最大累计伤害
- 转移:先放后回时新能量为 min(E, e-c_k+1);先回后放时先 min(E,e+1) 再扣 c_k
- 先确认回能与放技能的先后、初始能量,这决定转移细节和边界
- 复杂度 O(T·E),滚动数组空间 O(E);不可达状态初始化为负无穷
- T 远大于 E 时,用 (E+1) 维 max-plus 矩阵快速幂,复杂度 O(E³ log T)
易错点
- 忽略能量上限 E,回能后没有取 min,导致状态越界
- 不可达状态初始化为 0,会从不存在的能量状态错误转移
- 回能与放技能的先后顺序没确认,转移多算或少算 1 点能量
面试官常见追问
- 能不能贪心?
- 如果还要输出技能序列?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场