Number of Dice Rolls With Target Sum LeetCode solution in Java

1
class Solution {
2
  public int numRollsToTarget(int n, int k, int target) {
3
    if (target < n || target > n * k) return 0;
4
    if (n == 1) return 1;
5

6
    int[][] dp = new int[n + 1][n * k + 1];
7
    for (int i = 1; i <= k; i++) {
8
      dp[1][i] = 1;
9
    }
10
    int mod = 1000000007;
11
    for (int i = 2; i <= n; i++) {
12
      for (int j = i; j <= i * k && j <= target; j++) {
13
        for (int x = 1; x <= k; x++) {
14
          if (j - x >= 1) {
15
            dp[i][j] += dp[i - 1][j - x];
16
            if (dp[i][j] >= mod) {
17
              dp[i][j] %= mod;
18
            }
19
          }
20
        }
21
      }
22
    }
23
    return dp[n][target] % mod;
24
  }
25
}