两人轮流从两端取数的最大得分(预测赢家)
哪些公司问过
答案要点
- 区间 DP:dp[i][j] 为当前玩家在 [i, j] 上比对手多得的最大差值
- 转移:max(a[i] − dp[i+1][j], a[j] − dp[i][j−1])
- 初始 dp[i][i] = a[i],按区间长度递增计算
- 先手总得分 = (总和 + dp[0][n−1]) / 2
- 时间 O(n²),空间 O(n²) 可压缩为 O(n)
易错点
- 用贪心每次取两端较大值,不是最优策略
- 遍历顺序错误,用到了还没计算的长区间状态
- 忘记把差值换算回先手的实际得分
面试官常见追问
- 为什么用差值定义比直接定义得分更方便?
- 数组长度为偶数时先手是否必胜?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场