LeetCode 1155. N ways to roll dice one question per day

Problem description

Here you are  n  The same dice , Every dice has  k  Face to face , They are labeled as  1  To k .

Given three integers n ,  k and  target , Return to possible ways ( From a total of  kn  In different ways ) The number of rolling dice , Make the sum of the numbers facing up equal to  target .

The answer may be very big , You need to  109 + 7 modulus  .

Example 1：

Input ：n = 1, k = 6, target = 3
Output ：1
explain ： You throw one with 6 Face dice .
obtain 3 And there is only one way .
Example 2：

Input ：n = 2, k = 6, target = 7
Output ：6
explain ： You throw two dice , Each die has 6 Face to face .
obtain 7 And there are 6 Methods 1+6 2+5 3+4 4+3 5+2 6+1.
Example 3：

Input ：n = 30, k = 30, target = 500
Output ：222616187
explain ： The returned result must be right 109 + 7 modulus .
 

Tips ：

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/number-of-dice-rolls-with-target-sum
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Java 

class Solution {
    public int numRollsToTarget(int n, int k, int target) {
        int[][] dp = new int[n + 1][target + 1];
        int mod = (int)Math.pow(10,9) + 7;
        dp[0][0] = 1;
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= target;j++){
                for(int q = 1;q <= k;q++){
                    if(j >= q)
                        dp[i][j] = (dp[i][j] + dp[i - 1][j - q]) % mod;
                }
            }
        }
        return dp[n][target];
    }
}