https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/description
1155. Number of Dice Rolls With Target Sum
给你三个数字 n、k、target,n 表示丢几次骰子,k 表示骰子有几面(1~k点),target
表示目标点数,求出丢 n 次骰子后共有几种可能点数和为 target,因为数字很大所以
要取模运算。
思路:
1.如果骰子全骰到最大的和小于target,不用算可以直接返回 0。
2.定义 f(n, m) 表示使用 n 颗骰子和为 m 的方法数,很明显的 f(1, 1:k) 都是 1
,而当我们投一颗新骰子时每个点数会产生 k 个新的和,举例来说当骰子数为2时
可能是 1+1, 1+2, 1+3, ..., 1+k,所以我们遍历所有之前不为0(可以骰出来的数字)
的点数加上当前的点数做 n 轮之后检查 f(n, target) 即可。
Java Code: