LeetCode 1230. 抛掷硬币（DP）

1. 题目

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

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

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

示例 2：
输入：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 内，则被视为正确答案。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/toss-strange-coins
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• $dp[i][j]$ 表示 抛完第 i 枚后，有 j 个朝上的概率

class Solution {
public:
    double probabilityOfHeads(vector<double>& prob, int target) {
    	int n = prob.size(), i, j, k;
    	vector<vector<double>> dp(n+1, vector<double>(target+1, 0.0));
    	dp[0][0] = 1.0;//初始化
    	for(i = 0; i < n; ++i)
    		for(j = 0; j <= min(i,target); ++j)
			{
				dp[i+1][j] += dp[i][j]*(1-prob[i]);//下一枚是反面
                if(j+1 <= target)
				    dp[i+1][j+1] += dp[i][j]*(prob[i]);//下一枚是正面
			}
		return dp[n][target];
    }
};

124 ms 54.6 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

本文地址：https://blog.csdn.net/qq_21201267/article/details/107577040