Задача: 1230. Toss Strange Coins
Сложность: 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 {
    function probabilityOfHeads($prob, $target) {
        $n = count($prob);
        $dp = array_fill(0, $n + 1, array_fill(0, $target + 1, 0));
        $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];
    }
}

Ставь 👍 и забирай 📚 Базу знаний