面试题库 › 算法 / 大模型 › n个骰子点数和的所有取值与概率(DP)

n个骰子点数和的所有取值与概率(DP)

难度 ★★☆在 1 场真实面经中被问到 方向:算法 / 大模型考点:动态规划

哪些公司问过

字节跳动1

常见岗位:大模型算法

答案要点

  1. 状态dp[i][j]为i个骰子和为j的方案数,初始dp[1][1..6]=1
  2. 转移dp[i][j]=Σdp[i-1][j-k],k取1到6,只累加下标有效的项
  3. 和的取值为n到6n共5n+1个,概率为dp[n][s]/6^n
  4. 时间O(n²)(常数约36),滚动数组空间O(n),滑动窗口可省去6项累加
  5. 方案数可能超出long,可直接递推概率(每步乘1/6)避免溢出

易错点

面试官常见追问

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

相关面试题