1155. Number of Dice Rolls With Target Sum

题目信息

题号:

1155

难度:

Medium

主题:

动态规划、骰子、计数

原题:

LeetCode 1155

重点:

使用恰好 n 个相同的 k 面骰子;每个骰子的结果在 1 到 k,统计有序结果序列并对 10^9+7 取模

题目重述

给定 n 个相同的骰子,每个骰子有 k 个面,点数分别为 1 到 k。同时掷出全部骰子后,每个骰子的结果位置可区分,因此结果顺序不同属于不同方案。

请统计点数总和恰好等于 target 的方案数量,并返回对 10^9 + 7 取模后的结果。

1 <= n, k <= 30,1 <= target <= 1000。

自建示例

两个四面骰子得到总和五:

输入:n = 2, k = 4, target = 5
输出:4
解释:有序结果为 (1,4)、(2,3)、(3,2)、(4,1),共四种。

目标超过单个骰子的最大点数:

输入:n = 1, k = 6, target = 7
输出:0
解释:一个六面骰子的结果最多为 6,不可能得到总和 7。