http://leetcode.liangjiateng.cn/leetcode/toss-strange-coins/description
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:
Input: prob = [0.4], target = 1 Output: 0.40000
Example 2:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 Output: 0.03125
Constraints:
1 <= prob.length <= 10000 <= prob[i] <= 10 <= target<= prob.length- Answers will be accepted as correct if they are within
10^-5of the correct answer.
https://coordinate.wang/index.php/archives/2693/
有一些不规则的硬币。在这些硬币中，
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 <= 10000 <= prob[i] <= 10 <= target <= prob.length- 如果答案与标准答案的误差在
10^-5内，则被视为正确答案。
X.
dp[i][j] := prob of j coins face up after tossing first i coins.
dp[i][j] = dp[i-1][j] * (1 – p[i]) + dp[i-1][j-1] * p[i]
Time complexity: O(n^2)
Space complexity: O(n^2) -> O(n)
double probabilityOfHeads(vector<double>& prob, int target) {
const int n = prob.size();
vector<double> dp(target + 1);
dp[0] = 1.0;
for (int i = 0; i < n; ++i)
for (int j = min(i + 1, target); j >= 0; --j)
dp[j] = dp[j] * (1 - prob[i]) + (j > 0 ? dp[j - 1] : 0) * prob[i];
return dp[target];
}
Solution 2: Recursion + Memorization
Time complexity: O(n^2)
Space complexity: O(n^2)
Space complexity: O(n^2)
double probabilityOfHeads(vector<double>& prob, int target) {
vector<vector<double>> mem(prob.size() + 1, vector<double>(target + 1, -1));
function<double(int, int)> dp = [&](int n, int k) {
if (k > n || k < 0) return 0.0;
if (n == 0) return 1.0;
if (mem[n][k] >= 0) return mem[n][k];
const double p = prob[n - 1];
return mem[n][k] = p * dp(n - 1, k - 1) + (1 - p) * dp(n - 1, k);
};
return dp(prob.size(), target);
}
动态规划。首先假设dp[i][j]为投完第i枚硬币后有j枚硬币朝上的概率。如果第i-1枚硬币投完后有j枚朝上，那么第i枚硬币就只能朝下；如果i-1枚硬币投完后有j-1枚朝上，那么第i枚硬币就只能朝上。很容易建立状态转移方程，dp[i][j] = dp[i-1][j-1] * prob[i] + dp[i-1][j] * (1 - prob[i])。
(动态规划)
- 表示掷了前 i 个硬币，正面朝上次数为 j 的概率。
- 初始时，，其余为 0。
- 转移时，枚举这一次的结果，正面则 ，反面 。注意这里的
prob的下标是从 1 开始的。 - 最终答案为 。
时间复杂度
- 状态数共有 个，转移时间为常数，故总时间复杂度为 。
空间复杂度
- 和状态数相同，故时间复杂度为 。
- 可以通过滚动数组优化到 。
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];
}
X.
class Solution:
def probabilityOfHeads(self, prob: List[float], target: int) -> float:
n, res = len(prob), 0
def dfs(u, k, state):
nonlocal res
if k == target:
t = 1.0
for i in range(n):
if state & (1 << i):
t *= prob[i]
else:
t *= (1 - prob[i])
res += t
return
for i in range(u, n):
state |= (1 << i)
dfs(i + 1, k + 1, state)
state -= (1 << i)
dfs(0, 0, 0)
return res
但是这么做超时了，那么加记忆化呗！但是加了记忆化依旧超时，为什么？实际上上面代码的写法没有将问题归纳为多个重叠子问题，也就是没有递推公式。递推公式可以表示为：
按照这种思路去做的话，就可以写出如下代码。
from functools import lru_cache
class Solution:
def probabilityOfHeads(self, prob: List[float], target: int) -> float:
n = len(prob)
@lru_cache(None)
def dfs(u, k):
if k > target:
return 0.0
if u == n:
if k == target:
return 1.0
else:
return 0.0
res = 0
res += prob[u] * dfs(u + 1, k + 1)
res += (1 - prob[u]) * dfs(u + 1, k)
return res
return dfs(0, 0)
可以通过！！！这里我们就需要注意了，虽然都是
dfs的写法，但是不同的写法对于结果的影响非常大。通过记忆化加dfs解决的问题，也可以通过动态规划来做。而且这还是一个经典的01背包问题，对于每个元素考虑放和不放两种状态，而背包的容积就是target。class Solution:
def probabilityOfHeads(self, prob: List[float], target: int) -> float:
dp = [1] + [0] * target
for p in prob:
for k in range(target, -1, -1):
dp[k] = (dp[k - 1] if k else 0) * p + dp[k] * (1 - p)
return dp[-1]
public double probabilityOfHeads(double[] prob, int target) {
if(target==0){
double res = 1;
for(int i=0;i<prob.length;i++){
res *= (1 - prob[i]);
}
return res;
}
int N = prob.length;
double[][] dp = new double[target+1][N];
dp[0][0]=1-prob[0];
dp[1][0]=prob[0];
for(int j=1;j<N;j++){
for(int i=0;i<=target;i++){
dp[i][j]+=dp[i][j-1]*(1-prob[j]);
if(i>0) {
dp[i][j] += dp[i - 1][j - 1] * prob[j];
}
}
}
return dp[target][N-1];
}
这道题是一道典型的 dp 题，只需要按照一般 dp 的思路就行。
- 分析 dp 数组的坐标变量和范围。
- 分析最后返回的值在哪。
- 已知哪些值。
- 递推关系是什么？
