Сложность: medium
У вас есть несколько монет. Вероятность выпадения орла для i-й монеты равна prob[i].
Верните вероятность того, что количество монет, на которых выпал орел, равно target, если вы подбросите каждую монету ровно один раз.
Пример:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125
👨💻 Алгоритм:
1⃣Инициализация:
Создайте переменную n и инициализируйте её размером массива prob.
Создайте 2D массив dp размером n + 1 строк и target + 1 столбцов, где dp[i][j] хранит вероятность получить j орлов, используя первые i монет.
Установите базовый случай dp[0][0] = 1.
2⃣Итерация:
Используйте два вложенных цикла для заполнения массива dp.
Внешний цикл итерируется от i = 1 до n. Для каждого i установите dp[i][0], что обозначает вероятность получить 0 орлов при использовании i монет: dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]).
Внутренний цикл итерируется от j = 1 до target. Для каждого j вычислите dp[i][j] по формуле: dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]).
3⃣Возврат результата:
Верните значение dp[n][target], которое содержит искомую вероятность.
😎 Решение:
class Solution {
public double probabilityOfHeads(double[] prob, int target) {
int n = prob.length;
double[][] dp = new double[n + 1][target + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]);
for (int j = 1; j <= target && j <= i; j++) {
dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]);
}
}
return dp[n][target];
}
}Ставь 👍 и забирай 📚 Базу знаний