Jianbo Dai's

jz060.n个骰子的点数

 
  • Oct 19, 2020

题目链接

比较经典的动态规划题目，空间优化成一维矩阵。

这个算法的时间复杂度是O（N^2）其中N为骰子数，空间复杂度是O（N）。

class Solution:
    def twoSum(self, n: int) -> List[float]:
        res = [0] * n * 6
        for i in range(6):
            res[i] = 1
        for i in range(1, n):
            for j in range((i+1)*6-1, i-1, -1):
                if j >= 6:
                    res[j] = sum(res[j-6:j])
                else:
                    res[j] = sum(res[:j])
            for x in range(i):
                res[x] = 0
        s = sum(res[n-1:])
        return [x / s for x in res[n-1:]]
Search