当前位置： 移动技术网 > IT编程>开发语言>Java > LeetCode 1230. 抛掷硬币（DP）

LeetCode 1230. 抛掷硬币（DP）

2020年07月27日  | 移动技术网IT编程  | 我要评论

文章目录

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]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阿明），一起加油、一起学习进步！
Michael阿明

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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网