leetcode 1230

问题

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.

Example 1:

1
2
Input: prob = [0.4], target = 1
Output: 0.40000

Example 2:

1
2
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

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.

分析

$dp[i][j]$ 表示从 $0…i$ 个硬币中选出 $j$ 个正面朝上的概率。那个对于编号为 $i$ 的硬币就有两种状态，正面朝上和正面朝下。于是有状态转移方程:
$$
dp[i][j] = prob[i]dp[i-1][j-1] + (1-prob[i])dp[i-1][j]
$$
目标：$dp[n-1][target]$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 经过降为之后的代码
class Solution {
public:
    double probabilityOfHeads(vector<double>& prob, int target) {
        int n = prob.size();
        vector<double> dp(target+1, 0.0f);
        dp[0] = 1.0f-prob[0];
        if (target > 0) dp[1] = prob[0];
        
        for (int i = 1; i < n; ++i) {
            for (int j = min(i+1, target); j >= 0; --j) {
                dp[j] = (1.0f-prob[i])*dp[j];
                if (j>0) dp[j] += prob[i]*dp[j-1];
            }
        }
        return dp[target];
    }
};