发现字节特别喜欢考概率题和开放题，倒是不怎么考 LeetCode了（算法岗）

1. 投骰子连续两次是 6就停止，求投掷的次数的期望

解法1：动态规划 dp
听面试官说可以用 动态规划，但是没有思路…

看到其他大佬写的方法：

dp1(n) = 1/6 *1/6 * 5/6 [1-dp2(n-3)]
dp2(n) = dp2(n-1) + dp1(n)

其中 dp1 表示第几次停止的概率，dp2 表示前 n 次停止的概率
求出前三个初始值，就可以迭代了

解法2：使用马尔科夫链求解。

记“当已经掷出x次1朝上时，直至出现连续2次1朝上所需的期望次数”为E(x)。则有：
E(0) = 1 + 5/6 * E(0) + 1/6 * E(1)
E(1) = 1 + 5/6 * E(0) + 1/6 * E(2)
E(2) = 0
解释：由E(0)状态可转换成E(0)，E(1)状态（转换成E(2)状态的概率为零），E(0)转换成E(0)是指下一次投掷1不正面朝上，所以概率为5/6，E(0)转换成E(1)是指下一次投掷1正面朝上，所以概率为1/6，最前面的1表示一定投掷一次（然后状态会发生改变）。E(1),E(2)同理。

由上面三个式子可得：

E(0) = 42
表示初始状态——已经掷出0次1朝上时，直至出现连续2次1朝上所需的期望次数为E(0) = 42次。

2. 投硬币连续两次是正面就停止，求投掷的次数的期望

解0：
假设期望次数是E，我们开始扔，有如下几种情况：

• 扔到的是反面，那么就要重新仍，所以是0.5*(1 + E)
• 扔到的是正面，再扔一次又反面了，则是0.25*(2 + E)
• 扔到两次，都是正面，结束，则是0.25*2

所以递归来看 E = 0.5*(1 + E) + 0.25*(2 + E) + 0.25*2，解得E = 6

解1：
a[i]表示抛i次，最后一次是反面，而且这i次没有出现连续正面的情况的概率大小
f[i]表示正好抛i次，出现连续两次正面的概率大小
LEN越大，越逼近期望值

链接：https://www.nowcoder.com/questionTerminal/bfa0b0796e1847c8b36f96ad1614d4d0
来源：牛客网

int main()
{
    const int LEN = 100;
    double a[LEN], f[LEN];
    a[0] = 1;
    a[1] = 0.5;
    a[2] = 0.5;
    double E = 0.0;
    for (int i = 3; i < LEN; ++i) {
        a[i] = 0.5*a[i - 2] + 0.125*a[i - 3];
    }
    for (int i = 2; i < LEN; ++i) {
        f[i] = 0.25*a[i - 2];
        E += i*f[i];
    }
    cout<<E<<endl; 
    return 0;
}

解2：

解3：

解4：

3. 抛硬币直到出现连续N次正面为止的期望

参考:抛硬币 直到连续出现两次字为止

其他抛硬币问题系列变形

参考：几道抛硬币问题

参考：

1. 抛的硬币直到连续出现两次正面为止，平均要扔多少次

---

---

题主本硕机械专业，自学转互联网 算法岗成功，获得阿里、字节、美团、华为等 15+ offer
后续会在公众号 「苏学算法」分享各类学习笔记、面试经验，感兴趣的可以关注一波 😊 😊 😊～