技术

leetcode 1230.抛掷硬币

image.png

解题思路

  1. 这种类型的题目显然可以优化成最小结构，使用动态规划
  2. 最小结构： dp[i][j]: 抛掷i次硬币，j次正面的概率
  3. 状态转移方程： dp[i][j] = dp[i-1][j]*(1-(prob[i-1])) + dp[i-1][j-1]*prob[i-1] （注意这里第i次的概率对应数组index要-1）
  4. 边界条件分析，dp[0][0]=1

复杂度分析

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n^2) 认为row和col都为n

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
double probabilityOfHeads(double* prob, int probSize, int target){
    float** dp = (float**)malloc(sizeof(float*)*(probSize+1));
    for (int i = 0; i <= probSize; i++) {
        dp[i] = (float*)malloc(sizeof(float)*(target+1));
        (void)memset(dp[i], 0, sizeof(float)*(target+1));
    }
    dp[0][0] = 1;
    for (int i = 1; i <= probSize; i++) {
        for (int j = 0; j <= target; j++) {
            if (j > 0) {
                dp[i][j] = dp[i-1][j]*(1-prob[i-1]) + dp[i-1][j-1]*prob[i-1];
            } else {
                dp[i][0] = dp[i-1][0]*(1-prob[i-1]);
            }
        }        
    }
    return dp[probSize][target];
}