Leetcode1230 Toss Strange Coins

Posted on Edited on In

题目描述

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个必须朝下，于是我们很容易得到递推式:

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)
    //这边很容易出错，我们需要倒序遍历，否则之前的值(dp[j - 1])已经被修改
        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];
}