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: