擲骰子的N種方法
思路：
我們設定
dp［i］［j］
為考慮前i個骰子，達到總和為j的組合情況。
可以發現，對於每個組都有f種選法，而每一個組我們只能選擇一個值。當然如果
target>f*d || target 的情況，是找不到任何一種組合的，直接返回0。 一般化分析，對於 dp［i］［j］ 有如下的選擇“ 第i個骰子值為1， dp［i-1］［j-1］ 種情況 第i個骰子值為2， dp［i-1］［j-2］ 種情況 。。。 第i個骰子值為f，有 dp［i-1］［j-f］ 種情況 最終： dp［i］［j］ = sum（dp［i-1］［j-1］，dp［i-1］［j-2］，。。。，dp［i-1］［j-f］） 種選擇。 class Solution { int mod = （ int ） 1e9 + 7 ； public int numRollsToTarget （ int d ， int f ， int target ） { if （ target < d || target > d * f ） return 0 ； int ［］ dp = new int ［ target + 1 ］； //為第一行賦值 dp ［ 0 ］ = 1 ； for （ int i = 1 ； i <= d ； i ++） { for （ int j = target ； j >= 0 ； j ——） { dp ［ j ］ = 0 ； for （ int k = 1 ； k <= f ； k ++） { if （ j >= k ） { dp ［ j ］ += dp ［ j - k ］； dp ［ j ］ %= mod ； } } } } return dp ［ target ］； } } class Solution { int mod = （ int ） 1e9 + 7 ； public int numRollsToTarget （ int d ， int f ， int target ） { if （ target < d || target > d * f ） return 0 ； int ［］［］ dp = new int ［ d ］［ target + 1 ］； for （ int i = 1 ； i <= target ； i ++） { if （ i <= f ） dp ［ 0 ］［ i ］ = 1 ； } for （ int i = 1 ； i < d ； i ++） { for （ int j = target ； j >= 1 ； j ——） { for （ int k = 1 ； k <= f ； k ++） { if （ j >= k ） { dp ［ i ］［ j ］ += dp ［ i - 1 ］［ j - k ］； dp ［ i ］［ j ］ %= mod ； } } } } return dp ［ d - 1 ］［ target ］； } }
