n个骰子点数和的所有取值与概率(DP)
哪些公司问过
答案要点
- 状态dp[i][j]为i个骰子和为j的方案数,初始dp[1][1..6]=1
- 转移dp[i][j]=Σdp[i-1][j-k],k取1到6,只累加下标有效的项
- 和的取值为n到6n共5n+1个,概率为dp[n][s]/6^n
- 时间O(n²)(常数约36),滚动数组空间O(n),滑动窗口可省去6项累加
- 方案数可能超出long,可直接递推概率(每步乘1/6)避免溢出
易错点
- 把概率分母写成6n或5n+1,正确是6的n次方
- 转移时没处理j-k越界,或把i个骰子和的下界写成1而不是i
- 用int/long存方案数,n稍大即溢出
面试官常见追问
- 能用滑动窗口优化吗?
- n很大时如何避免溢出?
- 哪个点数和出现的概率最大?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场