837. 新 21 点 - Kotlin 动态规划

Problem: 837. 新 21 点

思路

不将思路局限于在大于k的情况里找可能性，先考虑这样一种情况：

如果题目为爱丽丝以 0 分开始，并在她的得分少于 k 分时抽取数字。在所有的分数情况中，爱丽丝的分数不超过n的概率为多少

对于初始化为，令i遍历0到k，对于任意都应当有，最后令所有的可能性之和除以所有可能性之和

以maxPts为2为例，我们设dp[0]=1，那么就有

• dp[0]派生得到dp[1]+=0.5，dp[2]+=0.5，二者之和为1
• dp[1]派生得到dp[2]+=0.25，dp[3]+=0.25，二者之和为0.5
• dp[2]派生得到dp[3]+=0.25，dp[4]+=0.25，二者之和为0.5
• …

这样很明显能看出，整个数组在这种计算方式下可能性之和是明显大于1的，而每个元素的意义实际上是它的权重而非概率，即dp[i]的含义为在所有情况中分数为i的权重

由于我们要在的情况里面寻找的情况，令所有的可能性之和除以的可能性之和即可

复杂度

时间复杂度:

空间复杂度:

Code

class Solution {
    fun new21Game(n: Int, k: Int, maxPts: Int): Double {
        val dp = DoubleArray(k + maxPts + 1) { i -> if (i != 0) (0).toDouble() else (1).toDouble() }
        val percent = ((1).toDouble() / maxPts)

        for (i in 0 until k) {
            for (j in 1..maxPts) {
                dp[i + j] += dp[i] * percent
            }
        }

        return (k..Math.min(n, k + maxPts)).map { dp[it] }.sum() / (k..k + maxPts).map { dp[it] }.sum()
    }
}