题目描述 You have some coins. The i-th coin has a probability prob[i] of facing heads when tossed.
Return the probability that the number of coins facing heads equals target if you toss every coin exactly once.
1 2 3 Example1: Input: prob = [0.4], target = 1 Output: 0.40000
1 2 3 Example2: Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 Output: 0.03125
1 2 Explanation: [[3,1]] is also accepted.
1 2 3 4 5 Constraints: 1 <= prob.length <= 1000 0 <= prob[i] <= 1 0 <= target <= prob.length Answers will be accepted as correct if they are within 10^-5 of the correct answer.
解析
题目是这样的,有一堆不均匀的硬币,问你正好target朝上的概率是多少?
这是一道典型的动态规划问题,多举出一些样例,或者根据基础的概率论,我们可以发现每个硬币都有正反两种可能性,而到第i个硬币正好有j个朝上的概率跟此前的状态有关,我们用dp[i][j]来表示,显然第i个硬币可以朝上或者朝下,如果朝上则前面得有j - 1个硬币朝上,才能保证此时有共有j个朝上,如果此前已经有j个朝上,则第i个必须朝下,于是我们很容易得到递推式:
d p ( i , j ) = d p ( i − 1 , j ) ∗ ( 1 − p ( i ) ) + d p ( i − 1 , j − 1 ) ∗ p ( i ) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public double probabilityOfHeads (double [] prob, int target) { double [][] dp = new double [prob.length][target + 1 ]; dp[0 ][0 ] = 1 - prob[0 ]; if (target >= 1 ) dp[0 ][1 ] = prob[0 ]; for (int i = 1 ; i < prob.length; i++){ for (int j = 0 ; j <= Math.min(i + 1 , target); j++){ if (j == 0 ) dp[i][j] = dp[i - 1 ][j] * (1.0 - prob[i]); else dp[i][j] = dp[i - 1 ][j] * (1.0 - prob[i]) + dp[i - 1 ][j - 1 ] * prob[i]; } } return dp[prob.length - 1 ][target]; }
不过这道题,还可以再做空间上的优化,我们发现求dp[i][j]只跟dp[i - 1][j - 1]与dp[i][j - 1]有关,遇到这种情况,我们可以把i利用循环优化掉,只保留j,即dp[j]表示此时有j个朝上的硬币的概率,于是我们可以得到更加简化的代码:
1 2 3 4 5 6 7 8 9 public double probabilityOfHeads (double [] prob, int target) { double [] dp = new double [target + 1 ]; dp[0 ] = 1.0 ; for (int i = 0 ; i < prob.length; ++i) for (int j = Math.min(i + 1 , target); j >= 0 ; --k) dp[j] = (j > 0 ? dp[j - 1 ] : 0 ) * prob[i] + dp[j] * (1 - prob[i]); return dp[target]; }