Skip to content

1230. Toss Strange Coins 👍

Approach 1: 2D DP

  • Time: $O(|\texttt{prob}||\texttt{target}|)$
  • Space: $O(|\texttt{prob}||\texttt{target}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  double probabilityOfHeads(vector<double>& prob, int target) {
    // dp[i][j] := the probability of tossing the first i coins with j heads
    vector<vector<double>> dp(prob.size() + 1, vector<double>(target + 1));
    dp[0][0] = 1.0;

    for (int i = 1; i <= prob.size(); ++i)
      for (int j = 0; j <= target; ++j)
        dp[i][j] = (j > 0 ? dp[i - 1][j - 1] * prob[i - 1] : 0) +
                   dp[i - 1][j] * (1 - prob[i - 1]);

    return dp[prob.size()][target];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
  public double probabilityOfHeads(double[] prob, int target) {
    // dp[i][j] := the probability of tossing the first i coins with j heads
    double[][] dp = new double[prob.length + 1][target + 1];
    dp[0][0] = 1.0;

    for (int i = 1; i <= prob.length; ++i)
      for (int j = 0; j <= target; ++j)
        dp[i][j] = (j > 0 ? dp[i - 1][j - 1] * prob[i - 1] : 0) + dp[i - 1][j] * (1 - prob[i - 1]);

    return dp[prob.length][target];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def probabilityOfHeads(self, prob: List[float], target: int) -> float:
    # dp[i][j] := the probability of tossing the first i coins with j heads
    dp = [[0] * (target + 1) for _ in range(len(prob) + 1)]
    dp[0][0] = 1.0

    for i in range(1, len(prob) + 1):
      for j in range(target + 1):
        dp[i][j] = (dp[i - 1][j - 1] * prob[i - 1] if j > 0 else 0) + \
            dp[i - 1][j] * (1 - prob[i - 1])

    return dp[len(prob)][target]

Approach 2: 1D DP

  • Time: $O(|\texttt{prob}||\texttt{target}|)$
  • Space: $O(|\texttt{target}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  double probabilityOfHeads(vector<double>& prob, int target) {
    // dp[j] := the probability of tossing the coins so far with j heads
    vector<double> dp(target + 1);
    dp[0] = 1.0;

    for (const double p : prob)
      for (int j = target; j >= 0; --j)
        dp[j] = (j > 0 ? dp[j - 1] * p : 0) + dp[j] * (1 - p);

    return dp[target];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
  public double probabilityOfHeads(double[] prob, int target) {
    // dp[j] := the probability of tossing the coins so far with j heads
    double[] dp = new double[target + 1];
    dp[0] = 1.0;

    for (final double p : prob)
      for (int j = target; j >= 0; --j)
        dp[j] = (j > 0 ? dp[j - 1] * p : 0) + dp[j] * (1 - p);

    return dp[target];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
  def probabilityOfHeads(self, prob: List[float], target: int) -> float:
    # dp[j] := the probability of tossing the coins so far with j heads
    dp = [1.0] + [0] * len(prob)

    for p in prob:
      for j in range(target, -1, -1):
        dp[j] = (dp[j - 1] * p if j > 0 else 0) + dp[j] * (1 - p)

    return dp[target]