Leetcode: 【每日一题】- 2020-07-15 - 来瓶可乐

[azl397985856]

冰箱 1 有 30 瓶可乐，冰箱 2 里有 31 瓶，60 天内随机在 1 、2 中拿走 1 瓶..，

60 天后冰箱 2 刚好剩下 1 瓶的概率是多少？

[yunlovebo]

如果按照概率的算法，我理解应该是C30 60 除以 C31 61，即60个里面取30个不排序 除以 61个里面取30个不排序，约分后=31/61，不知道对不对，另外求大佬的dp解法

[suukii]

我改过来了。

JavaScript Code

const test = (A, B) => {
    const dp = Array(A + 1)
        .fill(0)
        .map(() => Array(B + 1).fill(0))

    // 定义状态 dp[a][b] 为：拿了 a+b 瓶可乐，最后一瓶拿的是 B 可乐的概率
    // 所以 dp[0][b] 的概率都是 1
    dp[0] = dp[0].map((_, i) => (i === 0 ? 0 : 1))

    for (let a = 1; a < dp.length; a++) {
        for (b = 1; b < dp[0].length; b++) {
            // 因为 dp[a-1][b] 的下一步可能是 dp[a][b] 或者 dp[a-1][b+1]，
            // dp[a][b] 只是其中一个可能，所以要 * 0.5
            dp[a][b] = dp[a - 1][b] * 0.5 + dp[a][b - 1] * 0.5
        }
    }
    console.log(dp[A][B])
    return dp[A][B] // 0.5512890865042848
}
test(30, 31)

[azl397985856]

记忆化递归

from functools import lru_cache

@lru_cache(20)
def p(a, b):
    if a and b:
        return 0.5 * p(a - 1, b) + 0.5 * p(a, b - 1)
    return 0 if a else 1
p(30, 31) # 0.5512890865042848

复杂度分析

• 时间复杂度：$O(a * b)$
• 空间复杂度：$O(a * b)$

动态规划

def p(a, b):
    dp = [[0 if j == 0 else 1 for j in range(b + 1)] for _ in range(a + 1)]

    for i in range(1, a + 1):
        for j in range(1, b + 1):
            dp[i][j] = .5 * dp[i - 1][j] + .5 * dp[i][j - 1]

    return dp[-1][-1]
p(30, 31) # 0.5512890865042848

复杂度分析

• 时间复杂度：$O(a * b)$
• 空间复杂度：$O(a * b)$

优化的动态规划

def p(a, b):
    dp = [0 if j == 0 else 1 for j in range(b + 1)]

    for i in range(1, a + 1):
        for j in range(1, b + 1):
            dp[j] = .5 * dp[j] + .5 * dp[j - 1]

    return dp[-1]
print(p(30, 31)) # 0.5512890865042848

复杂度分析

• 时间复杂度：$O(a * b)$
• 空间复杂度：$O(b)$

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经30K star啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.