娱乐 每 周 概 率 挑 战 【第一期】

[applebird]

第一个很简单吧，从0出发1-6的概率都是1/6，然后从1出发将1的概率/6加到2-7上，跑个循环就可以得到每个格子路过的概率了，最后从里面找个max取出来

第二个和第三个不知道有没有精确解，但我感觉贪心应该是比较近似的，反正这个计算量不大，先贪心取一个，然后去掉这一个解把剩下的后面半段跑一遍前面的概率算法，再继续取一个直到满足条件。

第四个第五个思路是一样的，必须踩多少次感觉也不是很重要？和23的埋法应该是一样的

[applebird]

7 小时前, yhz012 说道:

第一问没问题

第二问和第三问是有精确解的，贪心取第一个之后，“去掉这一个解”的意思是？另外如果要用贪心的话，需要先证明贪心的正确性，即部分最优是全局最优？

第四问第五问和23问还是有一些区别的，2、3问的情况是一次就会死，所以不需要考虑连续踩坑的问题，但是4和5就不得不考虑了

 

极端一点的例子是，假设我埋6个坑，那1命的情况下，毫无疑问连挖6坑是最优解，但是2命的情况或许并不是最优解？

精确解的时间复杂度可能比较炸吧，最近大数据做多了都往近似里面去了，近似的话就是再重复一次第一问的算法，但是去掉了这一次选出的概率最大的坑，因为这个坑选过了，然后再往后推一遍，求个次大的

[applebird]

11 小时前, yhz012 说道:

精确解时间复杂度至少我现在手里能用的是O(n^5)级别。当然从结果反推，如果有一些证明，似乎可以压到O(1)不过常数项很大的级别

这个方法有一点问题

举例来说第一问答案是6，按照这个方法似乎只能找6之后的坑？但是实际上第二问答案是5、6

不是呀，是说去掉6之后6之前的概率不会变，6之后的发生了变化，因此重新求一下，最后选出最大的会发现是5

[applebird]

41 分钟前, yhz012 说道:

但是这样的话，最开始选6似乎就有问题了？

因为之所以最开始选6是因为6是没有坑的时候概率最大的

但是现在6前面有坑，所以6的概率也会变化？

 

数学一点的说法是最后答案是5和6，那么被坑的概率是P(5) + P(6 | not 5)，但是这里我们求的概率是P(5 | not 6) + P(6)，这两个是不等的

确实，但是这样应该可以在O（n）里面求出一个较为优的解？