1230. 抛掷硬币 - Kotlin 二维DP

Problem: 1230. 抛掷硬币

思路

设dp[i][j]为扔i枚硬币，其中j枚为正面向上的情况

边界条件：不考虑i为0的情况，当i为1时

令i遍历2到prob.size，j遍历0到i，对于任意j即前i枚硬币中有j枚为正面，有如下两种情况：

• 当第i枚硬币为正面时，其概率为前i-1枚硬币中有j-1枚为正面的可能性，乘以第i枚硬币为正面的可能性
• 当第i枚硬币为反面时，其概率为前i-1枚硬币中有j枚为正面的可能性，乘以第i枚硬币为反面的可能性

综合考虑，即

最后返回即可

复杂度

时间复杂度:

空间复杂度:

Code

class Solution {
    fun probabilityOfHeads(prob: DoubleArray, target: Int): Double {
        val dp = Array(prob.size + 1) { DoubleArray(prob.size + 1) { (0).toDouble() } }
        dp[1][1]=prob[0]
        dp[1][0]=1-prob[0]
        for (i in 2..prob.size) {
            for (j in 0..i) {
                dp[i][j] = (if (j > 0) dp[i - 1][j - 1] * prob[i - 1] else (0).toDouble()) + dp[i - 1][j] * (1 - prob[i - 1])
            }
        }
        return dp[prob.size][target]
    }
}