面试题库 › 客户端 › 两人轮流从两端取数的最大得分(预测赢家)

两人轮流从两端取数的最大得分(预测赢家)

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

哪些公司问过

字节跳动1

常见岗位:C++ / Qt 客户端

答案要点

  1. 区间 DP:dp[i][j] 为当前玩家在 [i, j] 上比对手多得的最大差值
  2. 转移:max(a[i] − dp[i+1][j], a[j] − dp[i][j−1])
  3. 初始 dp[i][i] = a[i],按区间长度递增计算
  4. 先手总得分 = (总和 + dp[0][n−1]) / 2
  5. 时间 O(n²),空间 O(n²) 可压缩为 O(n)

易错点

面试官常见追问

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

相关面试题