Leetcode: offer 60 Points of N dice [math + level DP + cumulative contribution]

analysis

The brute force solution will obviously time out
And then simply a1 + … + an = k(1 <= ai <= 6)(n <= k <= 6n) My math skills can't solve
therefore We turn to dp

dp(n, x) Express n A sieve and yes x Of , Set to t
that , It will contribute to the next level , So the next floor dp(n + 1, x + i) i belongs to [1, 6] Your contribution will add t / 6
/6 It is inevitable , Because each additional layer will have one more sieve , Just one more /6
The contribution is t Can continue dp(n, x) Of course, the difference between their sum must be 1 To 6 among
dp(n + 1, x + i) = dp(n, x) Add an arbitrary sieve So just multiply 1/6

ac code

class Solution:
    def dicesProbability(self, n: int) -> List[float]:
        #  level dp（ It's a contribution ）
        dp = [1 / 6] * 6

        for i in range(2, n + 1):
            tmp = [0] * (5 * i + 1) # (6i - i + 1)
            for j in range(len(dp)):
                for k in range(6):
                    tmp[j + k] += dp[j] / 6
            
            # update
            dp = tmp
        
        return dp

summary

For the first time dp
The result of the next layer is obtained by accumulating the contribution value