题目大意：
抛掷硬币
有一些不规则的硬币。在这些硬币中，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 内，则被视为正确答案。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1230
解题思路分析：
这又是一道标准的DP题目，使用递归加记忆数组同样可以求解。
对于每一枚硬币，抛出后都有两种可能，正面朝上或反面朝上。我们需要找出target个硬币使其正面朝上，剩下的反面朝上，其概率相乘即是一种可能性的概率。将所有可能性的概率相加即是结果。
递归时，创建记忆数组memo[][]，memo[i][j]代表从下标为i到数组末尾区间内j枚硬币正面朝上的概率。根据上面的分析，对于当前硬币只会出现两种可能，当正面朝上时：
res1 = prob[i] * memo[i+1][j-1]; // prob[i]为当前硬币正面朝上的概率 // memo[i+1][j-1]：当前硬币抛完后，进入下一个index，同时target消耗掉1个
当反面朝上时：
res2 = (1-prob[i]) * memo[i+1][j]; // (1-prob[i])为当前硬币正面朝下的概率 // memo[i+1][j]：当前硬币抛完后，进入下一个index，同时target没有消耗
两种情况的和即为当前结果。
看下实现代码：
Double[][] memo; // 记忆数组
public double probabilityOfHeads(double[] prob, int target) {
// 初始化记忆数组
memo=new Double[prob.length][target+1];
// 递归求解
return help(prob, target, 0);
}
// prob为概率数组
// t为当前还剩下的target
// index为当前下标
double help(double[] prob, int t, int index){
// 当t大于剩下数组长度时，表示剩下的硬币都是正面也无法满足条件
// 当t小于0时代表正面朝上的个数已经超过target了
// 返回0
if(t>prob.length-index || t<0) return 0;
// 递归结束条件
if(index==prob.length) return 1;
// 记忆数组若存在，直接返回
if(memo[index][t]!=null) return memo[index][t];
// 返回结果：
// 当前硬币正面朝下的概率
double res = (1-prob[index])*help(prob, t,index+1);
// 加上当前硬币正面朝上的概率
res+=prob[index]*help(prob, t-1,index+1);
memo[index][t]=res; // 将结果保存至记忆数组
return res;
} 本题解法执行时间为24ms。
Runtime: 24 ms, faster than 45.06% of Java online submissions for Toss Strange Coins.
Memory Usage: 51.5 MB, less than 100.00% of Java online submissions for Toss Strange Coins.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1230-toss-strange-coins-解题思路分析/