题目描述

有一些不规则的硬币。在这些硬币中，prob[i] 表示第 i 枚硬币正面朝上的概率。

请对每一枚硬币抛掷 一次，然后返回正面朝上的硬币数等于 target 的概率。

样例

输入：prob = [0.4], target = 1
输出：0.40000

输入：prob = [0.5,0.5,0.5,0.5,0.5], target = 0
输出：0.03125

限制

• 1 <= prob.length <= 1000
• 0 <= prob[i] <= 1
• 0 <= target <= prob.length
• 如果答案与标准答案的误差在 10^-5 内，则被视为正确答案。

算法

(动态规划) $O(n \times (target + 1))$

1. $f(i, j)$ 表示掷了前 $i$ 个硬币，正面朝上次数为 $j$ 的概率。
2. 初始时，$f(0, 0) = 1$，其余为 0。
3. 转移时，枚举这一次的结果，正面则 $f(i, j) = f(i, j) + f(i - 1, j - 1) * prob[i]$，反面 $f(i, j) = f(i, j) + f(i - 1, j) * (1 - prob[i])$。注意这里的 prob 的下标是从 1 开始的。
4. 最终答案为 $f(n, target)$。

时间复杂度

• 状态数共有 $O(n \times (target + 1))$ 个，转移时间为常数，故总时间复杂度为 $O(n \times (target + 1))$。

空间复杂度

• 和状态数相同，故时间复杂度为 $O(n \times (target + 1))$。
• 可以通过滚动数组优化到 $O(target + 1)$。

C++ 代码

class Solution {
public:
    double probabilityOfHeads(vector<double>& prob, int target) {
        int n = prob.size();
        vector<vector<double>> f(n + 1, vector<double>(target + 1, 0));

        f[0][0] = 1;

        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= target; j++) {
                if (j > 0)
                    f[i][j] += f[i - 1][j - 1] * prob[i - 1];
                f[i][j] += f[i - 1][j] * (1 - prob[i - 1]);
            }

        return f[n][target];
    }
};