Сложность: 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], которое содержит искомую вероятность.
😎 Решение:
func probabilityOfHeads(prob []float64, target int) float64 {
n := len(prob)
dp := make([][]float64, n+1)
for i := range dp {
dp[i] = make([]float64, target+1)
}
dp[0][0] = 1.0
for i := 1; i <= n; i++ {
dp[i][0] = dp[i-1][0] * (1 - prob[i-1])
for j := 1; j <= target; j++ {
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]
}Ставь 👍 и забирай 📚 Базу знаний