分享一道3月GG VO一道题

一个白人老大爷出的题
给一个N面的骰子 一个小

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

b就算获胜
求小人获胜的概率

dp[i] = sum_j( 1/N * dp[i+j] ), j 在范围[1,N]
初始化, dp[a..b] = 1, dp[b+1, ...] = 0

复杂度：a * N

请问这个1维坐标是何用?  
我理解[a, b]是距离起始点0的距离就是从a到b这一段?  扔骰子x次 * PickFrom(1-n)就是走的距离, 在a和b之间就算获胜? 所以如果b-a>N就100%获胜? 不知道理解的对不对.

eat板栗 发表于 2022-11-5 19:12
请问这个1维坐标是何用?  
我理解[a, b]是距离起始点0的距离就是从a到b这一段?  扔骰子x次 * PickFrom(1-n ...

对 是这样的 1维坐标只是用来标记小人位置

这难道不就是(b-a+1)/N 吗

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

好像比想象的复杂一些，可以考虑对每个点到达概率分别计算，首先给前N个数值概率设为1/N，然后从第一个点开始， 分别对后面N个点贡献当前概率的1/N，与各点概率相加。得到a之前K个点的概率然后分别计算每个点一次直接落在[a,b]之间的概率(不需要计算从靠前点多次投掷骰子到达[a,b]，因为后面的点已经加了前面点概率的1/N，多次投掷的概率会被算到后面的点位上)。不知道思路对不对。