投硬币的问题
连续投掷N次硬币，其中任意连续m次出现正面朝上次数最大值为x的概率是多少？如果x=m，那么就转化为N次中存在连续m次正面朝上的概率求解，本版已有答案。但是当x<m时怎么解，还请大家指教。 想到了一个动态规划算法。
记录最近$(m-1)$次抛出的正反面序列。
一共有$2^(m-1)$种序列。
记录每种序列出现的概率，空间复杂度为$O(2^m)$。
于是就可以计算再抛$1$次后，每种序列出现的概率。
一共要计算$N$次，时间复杂度为$O(N*2^m)$
不知道有没有多项式时间复杂度的算法。 1# 周瑜
所谓的任意连续m次正面朝上，是指这个连续的m次的整体的前后都不是正面的吗 的确表达上有问题，感觉不就是投掷m次有正好最大x次朝上的概率吗？
页:
[1]