Сложность: 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 {
func probabilityOfHeads(_ prob: [Double], _ target: Int) -> Double {
let n = prob.count
var dp = Array(repeating: Array(repeating: 0.0, count: target + 1), count: n + 1)
dp[0][0] = 1.0
for i in 1...n {
dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1])
for j in 1...target {
if j <= i {
dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1])
}
}
}
return dp[n][target]
}
}Ставь 👍 и забирай 📚 Базу знаний