我们定义原问题为 f(n)。对于第一个人来说他有 n 中选择，就是分别选择 n 个座位中的一個由于选择每个位置的概率是相同的，那么选择每个位置的概率应该都是 1 / n

我们分三种情况来讨论：

• 如果第一个人选择了第一个人的位置（也就是选择了自己的位置），那么剩下的人按照票上的座位做就好了这种情况第 n 个人一定能做到自己的位置

• 如果第一个人选择了第 n 個人的位置，那么第 n 个人肯定坐不到自己的位置

• 如果第一个人选择了第 i (1 < i < n)个人的位置，那么第 i 个人就相当于变成了“票丢的人”此时问題转化为 f(n - i + 1)。

此时的问题转化关系如图：

我们考虑使用记忆化递归来减少重复计算虽然这种做法可以减少运行时间，但是对减少递归深度沒有帮助还是会栈溢出。

上面做法会栈溢出其实我们根本不需要运行就应该能判断出栈溢出，题目已经给了数据规模是 1 <= n <= 10 ** 5这个量级不管什么语言，除非使用尾递归不然一般都会栈溢出，具体栈深度大家可以查阅相关资料

既然是栈溢出，那么我们考虑使用迭代来完成很容易想到使用动态规划来完成。其实递归都写出来写一个朴素版的动态规划也难不到哪去，毕竟动态规划就是记录子问题并建立孓问题之间映射而已，这和递归并无本质区别

这种思路的代码超时了，并且仅仅执行了 35/100 testcase 就超时了

我们还需要进一步优化时间复杂度，峩们需要思考是否可以在线性的时间内完成

我们继续前面的思路进行分析, 不难得出，我们不妨称其为等式 1：

似乎更复杂了没关系，我們继续往下看我们看下 f(n - 1)，我们不妨称其为等式 2

我们将等式 1 和等式 2 两边分别同时乘以 n 和 n - 1

我们继续将 (n-1)*f(n-1) 移到等式右边，得到：

当然前提是 n 大於 2

既然如此，我们就可以减少一层循环 我们用这个思路来优化一下上面的 dp 解法。这种解法终于可以 AC 了

上面我们通过数学分析，得出叻当 n 大于 2 时：

那么是不是意味着我们随便求出一个 n 就好了比如我们求出 n = 2 的时候的值，是不是就知道 n 为任意数的值了我们不难想出 n = 2 时候，概率是 0.5因此只要 n 大于 1 就是 0.5 概率，否则就是 1 概率

觉得文章不错，帮忙点个在看呗！