1230. Toss Strange Coins

leetcode medium

#array#backtracking#csharp#dynamic-programming#leetcode#medium#string

Task

У вас есть несколько монет. Вероятность выпадения орла для i-й монеты равна prob[i].

Верните вероятность того, что количество монет, на которых выпал орел, равно target, если вы подбросите каждую монету ровно один раз.

Пример:

Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0

Output: 0.03125

C# solution

matched/original

public class Solution {
    public double ProbabilityOfHeads(double[] prob, int target) {
        int n = prob.Length;
        double[][] dp = new double[n + 1][];
        for (int i = 0; i <= n; i++) {
            dp[i] = new double[target + 1];
        }
        dp[0][0] = 1.0;
        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) {
                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];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public double ProbabilityOfHeads(double[] prob, int target) {
        int n = prob.size();
        double[][] dp = new double[n + 1][];
        for (int i = 0; i <= n; i++) {
            dp[i] = new double[target + 1];
        }
        dp[0][0] = 1.0;
        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) {
                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];
    }
}

Java solution

matched/original

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];
    }
}

Explanation

Algorithm

Инициализация:

Создайте переменную n и инициализируйте её размером массива prob.

Создайте 2D массив dp размером n + 1 строк и target + 1 столбцов, где dp[i][j] хранит вероятность получить j орлов, используя первые i монет.

Установите базовый случай dp[0][0] = 1.

Итерация:

Используйте два вложенных цикла для заполнения массива 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]).

Возврат результата:

Верните значение dp[n][target], которое содержит искомую вероятность.

😎