N个座位坐满人的期望

公交车上有一排 n 个座位，这一排的 n 个座位有个规定：乘客选中落座的前后位置，不允许坐人。即如果某位置的相邻位置有其他乘客，则该座位不会被选择。1 号座位与 2 号相邻，n 号座位与 n-1 号相邻，除了 1 号与 n 号座位，任意 i 号座位都与 i-1 和 i+1 号座位相邻。乘客源源不断的依次上车，每次上一人，随机选符合规定的座位，求这个n个座位坐满人的期望。

示例分析

n=1 时，共有1种坐满人的坐法，坐满时的总人数为1，期望=$\frac{1}{1}=1$

n=2 时，共有2种坐满人的坐法，坐满时的总人数为2，期望=$\frac{2}{2}=1$

n=3 时，共有3中坐满人的坐法，坐满时的总人数为5，期望=$\frac{5}{3} \approx 1.67$

• 第一种坐法: 第一个乘客选择中间位置坐，后来乘客按规则，无法选中第一和第三个座位，该坐法共有1人落座。
• 第二种坐法：第一个乘客选择第一个位置，第二个乘客则只能选择最后一个位置，该坐法共有2人落座。
• 第三种坐法：第一个乘客选择组后一个位置，第二个乘客则只能选择第一个位置，该坐法共有2人落座。

从示例易得，期望的计算公式, $h_i(n)$分别为 n 个座位时，第 i 个坐法可以落座的人数, N为坐法的数量

\[E(n) = \frac{\sum_{i=1}^{N}h_i(n)}{N}\]

因此，问题的关键是求出座位数量为 n 时的所有坐法数量，以及每种坐法对应的落座人数。

子问题

假如已经知道 n 个座位时的所有坐法，出于临时需要，公交车上在最后临时增加了一个座位（第n+1个座位），由于规则的限制：落座的前后无法入座，新增的第n+1个座位能否落座，取决于第n个座位是否有人落座。 因此，第n个位置（最后一个位置）是否有人落座，需要成为标记子问题的一个变量或者状态，子问题的状态值是其因变量。

令：$f_1(n)$ 表示 n个座位时，最后一个座位坐人时的方法数； $f_2(n)$表示n个座位时，最后一个座位不坐人时的方法数。 $h_1(n)$表示 n个座位时，最后一个座位坐人时，可落座的座位数量；$h_2(n)$表示n个座位时，最后一个位置不坐人时，可落座的座位数量。

n=1时：$h_1(1)=1, h_2(1)=0, f_1(1)=1, f_2(1)=0$

n=2时：$h_1(2)=1, h_2(2)=1, f_1(2)=1, f_2(2)=1$

	$n_1$	$n_2$
i=1	[1]	[]
i=2	[]	[1]

$n_1$, $n_2$ 表示第一、第二个座位，第一列标记i=1, i=2 表示第一、第二个坐法，[]表示座位不可入座，[1]表示该座位可入座且被第一个人入座， 例如，当i=1时，在该坐法下，第一个座位可以坐人，但因为只有该位置可以坐人，所以该只有一种坐法。

n=3时, 落座方案数和可落座状态

	$n_1$	$n_2$	$n_3$
i=1	[]	[1]	[]
i=2	[1]	[]	[2]
i=3	[2]	[]	[1]

n=3时，当最后一个位置可以落座时，可落座的状态，只需从n=2时，最后一个位置不可落座时的状态转移过来（将第三个可入座的座位放在第二个不可入座的座位之后），就可满足约束条件。此时，可落座的位置数量为 h_1(3) = $h_2(2) + 1 = 2$。

由于第三个位置可以落座，此时第一个用户可以选择第一个座位和第三个座位入座，有两种选择，第二个用户只有一种选择，可落座的方法数量为 2。 从座位的角度看, 新增座位后有两个座位可入座，所以新增座位也有两种选择：第一个用户入座，第二个用户入座；可落座的座位数量 等价于 新增座位的选择方法数，所以$f_1(3)=f_2(2) \times h_1(3) = 2$。

同理，n=3时，当最后一个位置不可落座时, 由于没有新的位置可以落座，此时可落座的座位数量，就是n=2时的最后一个位置可坐人时的可落座数量: $h_2(3) = h_1(2) = 1$, 入座的方法数量: $f_2(3) = f_1(2)$

n=4时，落座方案数和可落座状态

	$n_1$	$n_2$	$n_3$	$n_4$
i=1	[]	[1]	[]	[2]
i=2	[1]	[]	[2]	[]
i=3	[2]	[]	[1]	[]
i=4	[]	[2]	[]	[1]

n=5时，落座方案数和可落座状态

	$n_1$	$n_2$	$n_3$	$n_4$	$n_5$
i=1	[]	[1]	[]	[2]	[]
i=2	[1]	[]	[2]	[]	[3]
i=3	[2]	[]	[1]	[]	[3]
i=4	[]	[2]	[]	[1]	[]
i=5	[2]	[]	[3]	[]	[1]
i=6	[1]	[]	[3]	[]	[2]
i=7	[3]	[]	[1]	[]	[2]
i=8	[3]	[]	[2]	[]	[1]

综上分析，得到状态转移公式：

\[\begin{align*} & h_1(n) = h_2(n-1) + 1 \\ & h_2(n) = h_1(n-1) \\ & f_1(n) = f_2(n-1) * h_1(n) \\ & f_2(n) = f_1(n-1) \\ & E(n) = \frac{f_1(n) \times h_1(n) + f_2(n) \times h_2(n)}{f_1(n) + f_2(n)} \end{align*}\]

代码

double solve(int n) {
    vector<int> h1(n+1), h2(n+1); // 最后一个位置坐人/不坐人的可坐座位数量
    vector<int> f1(n+1), f2(n+1); // 最后一个位置坐人/不坐人的方法数
    if(n<1) return -1; // invalid
    h1[1] = 1; h2[1] = 0;
    f1[1] = 1; f2[1] = 0;
    
    h1[2] = 1; h2[2] = 1;
    f1[2] = 1; f2[2] = 1;
    if (n==1 || n==2) {
        return (h1[n] * f1[n] + h2[n]*f2[n])*1. / (f1[n] + f2[n]);
    }
    for(int i=3; i<=n; ++i) {
        h1[i] = h2[i-1] + 1; h2[i] = h1[i-1];
        f1[i] = f2[i-1] * h1[i]; f2[i] = f1[i-1];
    }
    return (f1[n] * h1[n] + f2[n] * h2[n]) * 1. / (f1[n]+f2[n]);
}

// 状态压缩
double solve(int n) {
    int h1, h2; // 最后一个位置坐人/不坐人的可坐座位数量
    int f1, f2; // 最后一个位置坐人/不坐人的方法数
    if(n<1) return -1; // invalid
    // n=1时
    if (n== 1) {
       h1 = 1; h2 = 0;
       f1 = 1; f2 = 0;
    }
    if (n==2) {
       h1 = 1; h2 = 1;
       f1 = 1; f2 = 1;
    }
    if (n==1 || n==2) {
        return (h1 * f1 + h2 * f2)*1. / (f1 + f2);
    }
    for(int i=3; i<=n; ++i) {
        int old_h1 = h1;
        h1 = h2 + 1; h2 = old_h1;
        int old_f1 = f1;
        f1= f2 * h1; f2 = old_f1;
    }
    return (f1 * h1 + f2 * h2) * 1. / (f1+f2);
}

其他解法

地铁上一排n个座位坐满人的期望 （最后f(n)的递推公式少了系数2）

令：$f(n)$为座位数量为n时候的期望, n个座位时，第一个人上车，有n种类选择：

选择第一个位置时，期望=$\frac{1}{n}(1 + f(n-2))$

选择第二个位置时，期望=$\frac{1}{n}(1 + f(n-3))$

选择第三个位置时，期望=$\frac{1}{n}(1 + f(n-4) + f(1))$

选择第四个位置时，期望=$\frac{1}{n}(1 + f(n-5) + f(2))$

…

选择第n-2个位置时，期望=$\frac{1}{n}(1+f(1)+f(n-4))$

选择第n-1个位置时，期望=$\frac{1}{n}(1+f(2)+f(n-5))$

选择第n个位置时，期望=$\frac{1}{n}(1+f(n-2))$

将选择所有位置的期望相加: $f(n) = \frac{2}{n}(f(1) + f(2) + … + f(n-2)) + 1$

double solve(int n) {
  vector<double> f(n+1);
  f[0]=0,f[1]=1,f[2]=1;
  for(int i=3;i<=n;i++) {
    double sum = 0;
    for(int k=1; k<=i-2; ++k){
      sum += f[k];
    }	
    f[i] = ((2. / i ) * sum) + 1.;	
  }
  return f[n];
}

两种解法结果不一致原因分析

比较两种解法在n取不同值的时候的结果

	第一种	第二种
n=3	1.667	1.667
n=4	2	2
n=5	2.75	2.467
n=6	3	2.88889
n=7	3.8	3.32381
n=8	4	3.75556
n=9	4.8333	4.18801

为什么两种解法不一致？？

在第一种解法中，第 n 个座位时的入座方法数状态只考虑从第 n-1 座位时的入座方法数状态转移过来，无形中添加了顺序的限制，这样其实限制了乘客选择座位的顺序。例如当n=5时，第一个乘客选择了座位1，第二个乘客按照顺序选择，则只能选择座位3，而不能选择座位4、座位5。 针对这个问题，选择在有$x$个座位可入座时，引入全排列$x!$，即：$f_1(n)=f_2(n-1) \times h_1(n), f_2(n) = f_1(n-1)$，顺序的问题算是解决了。

在第一种解法中，只考虑了相邻入座乘客间隔1个空座的情况，这相当于求解n个座位最多可入乘客的期望。 题目中没有这样限制条件，因此，第一种解法中少考虑了相邻入座乘客间隔2个空座 以及 同时存在间隔1个空座、2个空座的情况。

只考虑相邻入座乘客间隔1个空座时，最后一个位置是否入座可以将可入座座位数量分成两类，每一类中可入座数量相同。当考虑间隔两个空座时，$h_1(n), h_2(n)$ 则不够用了，$x$个间隔2个空座的情况 X $y$ 个间隔1个空座的情况，组合数量太多，分析过于繁琐。

比如，在满足前后无人的要求下，第 n 个状态也能从第n-3个状态转移出来。例如,当n=5时，当第五个座位可以坐人时，从n=2时的状态转移过来，此时，n=2状态下的最后一个可入座座位 和第5个座位之间的座位是否可入座，依赖第五个座位和n=2时最后一个可入座座位的位置序号，当选择他们中间的某个合法位置落座时，可落座的区间变成了两个，这样的分析起来非常复杂。

后记

该题目来自与中国某互联网金融大厂面试题，面试时没有AC出，遂记下，徐图之。