package leetcode;

/**
 * https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
 */
public class Problem1155 {
    public int numRollsToTarget(int d, int f, int target) {
        return numRollsToTarget(d, f, target, 0, new Integer[/*dice*/ 31][/*sum*/ 1001]) % 1_000_000_007;
    }

    private static int numRollsToTarget(int dice, int faces, int target, int sum, Integer[][] memo) {
        if (dice == 0) {
            return sum == target ? 1 : 0;
        }
        if (memo[dice][sum] != null) {
            return memo[dice][sum];
        }
        int count = 0;
        for (int i = 1; i <= faces; i++) {
            count += (numRollsToTarget(dice - 1, faces, target, sum + i, memo)) % 1_000_000_007;
        }
        memo[dice][sum] = count % 1_000_000_007;
        return count % 1_000_000_007;
    }

    public static void main(String[] args) {
        Problem1155 prob = new Problem1155();
        System.out.println(prob.numRollsToTarget(1, 6, 3)); // 1
        System.out.println(prob.numRollsToTarget(2, 6, 7)); // 6
        System.out.println(prob.numRollsToTarget(2, 5, 10)); // 1
        System.out.println(prob.numRollsToTarget(1, 2, 3)); // 0
        System.out.println(prob.numRollsToTarget(30, 30, 500)); // 222616187
    }
}

@@ -193,16 +193,23 @@
  return 
+(int) (
 numRolls
@@ -238,23 +238,20 @@
  0, new 
-Integer
+Long
 %5B/*dice*
@@ -278,32 +278,33 @@
  %25 1_000_000_007
+)
 ;%0A    %7D%0A%0A    pri
@@ -315,19 +315,20 @@
  static 
-int
+long
  numRoll
@@ -383,15 +383,12 @@
 um, 
-Integer
+Long
 %5B%5D%5B%5D
@@ -566,19 +566,20 @@
         
-int
+long
  count =
@@ -763,32 +763,16 @@
  = count
- %25 1_000_000_007
 ;%0A      
@@ -789,461 +789,9 @@
 ount
- %25 1_000_000_007;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1155 prob = new Problem1155();%0A        System.out.println(prob.numRollsToTarget(1, 6, 3)); // 1%0A        System.out.println(prob.numRollsToTarget(2, 6, 7)); // 6%0A        System.out.println(prob.numRollsToTarget(2, 5, 10)); // 1%0A        System.out.println(prob.numRollsToTarget(1, 2, 3)); // 0%0A        System.out.println(prob.numRollsToTarget(30, 30, 500)); // 222616187
+;
 %0A   

Solve problem 1155