七夕，你跟女神邂逅的概率有多大？

    七夕刚过，女神追到了么？如果还差一点点，不要气馁，大神以洪荒之力向你证明追到女神是大概率事件。大神，当然就是小明:)

套路

    小明追着女神来到某旅游城市，这个城市有十大景点，女神每天随机去一个不同的景点，10天后离开。小明为了邂逅女神也决定接下来十天每天随机去一个不同景点。 请问小明有多大概率在这十天里邂逅女神。（假定同一天在同一景区就算邂逅)

分析

    我们把十天看成一个整体（十天看做一次实验），用表示女神的一个随机安排，用表示小明的一个随机安排。

    容易看出，对于这个安排，小明要邂逅女神，则需要满足任意有一天i，有 ai=bi,可以是多天相遇，也可以是单独一天相遇。这样分析起来考虑情况较多。

换一个思路，我们考虑不相遇的概率p多大，最后用1-p就是我们原本要求的概率。

    对于女神的任意一个随机安排， 小明的安排要满足任取i, ai!=bi， 我们假定有F(10)种安排b使得任取i,bi!=ai。 那么所求概率为F(10)/P(10). P(10)为10的全排列，也就是小明的所有可能安排数。

    分析到这，急性子可能直接就写代码了， 搜索出所有满足性质的排列个数。 等价于给定 1-10十个数，把这十个数排成一排，使得1不在第一个位置，2不在第二个位置。。。

    代码如下：

更进一步

    这个解法太暴力了，但也考察了搜索算法的基本功底。 我们回到这个题， 更进一步， 我们给定1-N,N个数.

    要求 所有这N个数的排列数，使得i不排在第i个位置。（错位排列问题)

我们用F(N)来表示这个数，显然F(1)=0, F(2)=1.

    我们考虑第n个数，他可以放在其他（N-1)个位置中的任意一个，假设是第k个位置。

现在对第k个数的两种情况分别讨论：

1. k安排在第n个位置， 那么剩下的数的要满足要求排列的话，总数正好是规模为N-2的错位排列数,F(N-2)

2. k不是在第n个位置，那么相当于我们要求k不能排在第n个位置，其他的仍然是i不能排在第i个位置，
   我们可以把第n个位置看成新的'第k个位置', 显然问题等价于规模为N-1的，错位排列个数，F(N-1)

    综合起来，F(N)=(N-1)*(F(N-2)+F(N-1)).

    分析到这我们可以写出更好的动态规划算法了。

扩展

上面给出的递推公式可以求解的，可以直接给出通项公式，感兴趣的同学可以搜索下， 这里直接给出

F(N)=[N!/e + 0.5]

代入， p=([N!/e + 0.5]/N!), N够大时， 约等于 1/e， 从而相遇概率为1-1/e=0.63。

神奇！

e真是无处不在！

真爱永在！

向心中有爱的人推荐：待字闺中。

一个由陈利人和他的朋友共同创建的公众号【待字闺中】，深度分析大数据、深度学习、人工智能等技术，切中实际应用场景，为大家授业解惑，间或，还会介绍国内外相关领域有趣的面试题。推荐大家关注。