1155.掷骰子等于目标和的方法数

链接：1155.掷骰子等于目标和的方法数
难度：Medium
标签：动态规划
简介：给定三个整数 n , k 和 target ，返回可能的方式(从总共 kn 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。

题解 1 - python

• 编辑时间：2023-10-24
• 执行用时：84ms
• 内存消耗：18.8MB
• 编程语言：python
• 解法介绍：记忆化递归，记录当前序号和剩余目标。

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        @cache
        def dfs(idx: int, target: int) -> int:
            if idx == n: return target == 0
            return sum(dfs(idx + 1, target - i) for i in range(1, min(k, target) + 1)) % (10 ** 9 + 7)
        return dfs(0, target)