解法一：递归

题目描述的可以作为n阶问题。

  • 当n=1时，ans=1.0。
  • 当n=2时，ans=0.5。
  • 当n>=3时，可以转换为子问题求解。第一个人选择任何一个座位的几率都是1/n。

如果他选择了本来就属于他的座位，那么所有人都能得到正确的座位，第n个人得到自己座位的几率为1。
如果他选择了第n个人的座位，那么第n个人得到自己座位的几率为0。
如果他选择了第i个人的座位，2<=i<=n-1，那么其实对于第2到i-1这些人，是没有干扰的，他们都能选择到正确的座位，此时问题转化为(n-i+1)阶子问题。

以下是直接递归的写法，不存储结果进行剪枝，会超时。

  1. class Solution {
  2.     public double nthPersonGetsNthSeat(int n) {
  3.         if (n == 1) {
  4.             return 1.0;
  5.         } else if (n == 2) {
  6.             return 0.5;
  7.         } else {
  8.             double ans = 1.0 / n;
  9.             for (int i = 2; i <= n - 1; ++i) {
  10.                 ans += nthPersonGetsNthSeat(n - i + 1) / n;
  11.             }
  12.             return ans;
  13.         }
  14.     }
  15. }

其实计算几个低阶问题就可以发现规律，可以通过数学归纳法证明。

  1. class Solution {
  2.     public double nthPersonGetsNthSeat(int n) {
  3.         if (n == 1) {
  4.             return 1.0;
  5.         } else {
  6.             return 0.5;
  7.         }
  8.     }
  9. }