硬币问题

题目

给定 n 枚硬币 (n 为奇数)，编号为 1, 2, · · · , n。投掷第 i 枚硬币时有 pi 的概率正面朝上，有 1 − pi 的概率反面朝上。 设计算法求解投掷这 n 枚硬币，其中正面朝上的硬币数量多于反面朝上的概率，并分析该 算法的时间复杂度

解题

这道题使用动态规划来做。

首先创建dp[n + 1][n + 1]数组，其中dp[i][j] 表示丢了i个硬币，有j个硬币朝上，

其次，对状态进行初始化，再进行状态转移，最后返回

状态转移方程：

分析可知，时间复杂度为O(n^2)

public double coin(double[] p) {
    int n = p.length;
    //dp[i][j] : 投了i个硬币有j个硬币朝上的概率
    double[][] dp = new double[n + 1][n + 1];
    Arrays.fill(dp[0], 1);
    dp[1][0] = 1 - p[0];
    dp[1][1] = p[0];
    for (int i = 2; i <= n; i++) {
        dp[i][0] = dp[i - 1][0] * (1 - p[i - 1]);
        for (int j = 1; j <= i; j++) {
            dp[i][j] = dp[i - 1][j] * (1 - p[i - 1]) + dp[i - 1][j - 1] * p[i - 1];
        }
    }
    double sum = 0.0;
    for (int i = n / 2 + 1; i <= n; i++) {
        sum += dp[n][i];
    }
    return sum;
}