没看懂leetcode大牛关于一道概率题的答案# JobHunting - 待字闺中
f*m
1 楼
原帖：
http://www.mitbbs.com/article_t1/JobHunting/32293265_0_1.html
题目：
给一个筛子， 最大可以抛3次， 每次可以选择是否继续丢， 给一个策略让最后筛子的
点数最大化。
比如如果第一次丢就得到1点，很明显需要继续下去
如果第一次丢得到6点，很明显没必要继续下去，因为后面再丢的两次最大也不会超过
六点
如果第一次丢得到5点，可能要考虑是不是博一下了。
扩展问题是把3次推广到N次。
*****
Leetcode大牛给的答案：
给个数学公式。这道题应该也可以用递推来解，但还没想清楚怎么弄。
Define:
n = number of trials.
m = max value of all trials.
P(m, n) = (1/6^n) * Sum(k = 1 .. n) C(n, k) * (m - 1)^(n - k)
Therefore,
Expected value of max value after n trials:
E = Sum(k = 1 .. 6) k * P(k, n)
E(Max when Trials = 1) = 3.5
E(Max when Trials = 2) = 4.4722
E(Max when Trials = 3) = 4.9583
E(Max when Trials = 4) = 5.2446
所以，只要看期望值，就知道需不需要再扔筛子了。
《〈〈〈〈〈〈〈〈〈〈〈〈〈〈〈
请问各位公式中(m - 1)^(n - k)是怎么来的？
谢谢。
http://www.mitbbs.com/article_t1/JobHunting/32293265_0_1.html
题目：
给一个筛子， 最大可以抛3次， 每次可以选择是否继续丢， 给一个策略让最后筛子的
点数最大化。
比如如果第一次丢就得到1点，很明显需要继续下去
如果第一次丢得到6点，很明显没必要继续下去，因为后面再丢的两次最大也不会超过
六点
如果第一次丢得到5点，可能要考虑是不是博一下了。
扩展问题是把3次推广到N次。
*****
Leetcode大牛给的答案：
给个数学公式。这道题应该也可以用递推来解，但还没想清楚怎么弄。
Define:
n = number of trials.
m = max value of all trials.
P(m, n) = (1/6^n) * Sum(k = 1 .. n) C(n, k) * (m - 1)^(n - k)
Therefore,
Expected value of max value after n trials:
E = Sum(k = 1 .. 6) k * P(k, n)
E(Max when Trials = 1) = 3.5
E(Max when Trials = 2) = 4.4722
E(Max when Trials = 3) = 4.9583
E(Max when Trials = 4) = 5.2446
所以，只要看期望值，就知道需不需要再扔筛子了。
《〈〈〈〈〈〈〈〈〈〈〈〈〈〈〈
请问各位公式中(m - 1)^(n - k)是怎么来的？
谢谢。
