Leetcode 1155:掷骰子的N种方法(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1155:掷骰子的N种方法(超详细的解法!!!)

in leetcode with 0 comment

这里有 d 个一样的骰子,每个骰子上都有 f 个面,分别标号为 1, 2, ..., f

我们约定:掷骰子的得到总点数为各骰子面朝上的数字的总和。

如果需要掷出的总点数为 target,请你计算出有多少种不同的组合情况(所有的组合情况总共有 f^d 种),模 10^9 + 7 后返回。

示例 1:

输入:d = 1, f = 6, target = 3
输出:1

示例 2:

输入:d = 2, f = 6, target = 7
输出:6

示例 3:

输入:d = 2, f = 5, target = 10
输出:1

示例 4:

输入:d = 1, f = 2, target = 3
输出:0

示例 5:

输入:d = 30, f = 30, target = 500
输出:222616187 

提示:

解题思路

这个问题首先不难想到通过DFS来做。我们可以定义函数$f(i,j)$,其中$i$表示几个骰子,$j$表示我们的目标值是多少。那么

然后通过记忆化的方式加速计算即可。

from functools import lru_cache
class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        mod = 10**9 + 7
        
        @lru_cache(None)
        def dfs(m, t):
            if m < 0 or t < 0:
                return 0
            if m == 0 and t == 0:
                return 1
            
            res = 0
            for i in range(1, f + 1):
                res = (res + dfs(m - 1, t - i)) % mod
            return res
        return dfs(d, target)

我们也可以通过动态规划的方式来写

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        mod = 10**9 + 7
        mem = [[0]*(target + 1) for _ in range(d + 1)]
        mem[0][0] = 1
        for i in range(1, d + 1):
            for j in range(1, f + 1):
                for k in range(j, target + 1):
                    mem[i][k] = (mem[i][k] + mem[i-1][k-j]) % mod
        return mem[-1][-1]

但是动态规划的效率没有前一种高。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses