@@ -0,0 +1,2251 @@
+//  Copyright 2021 The KeepTry Open Source Project%0A//%0A// Licensed under the Apache License, Version 2.0 (the %22License%22);%0A// you may not use this file except in compliance with the License.%0A// You may obtain a copy of the License at%0A//%0A//     http://www.apache.org/licenses/LICENSE-2.0%0A//%0A// Unless required by applicable law or agreed to in writing, software%0A// distributed under the License is distributed on an %22AS IS%22 BASIS,%0A// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.%0A// See the License for the specific language governing permissions and%0A// limitations under the License.%0A//%0A%0Apackage dp;%0A%0Aimport java.util.HashMap;%0Aimport java.util.Map;%0A%0Apublic class Leetcode1155NumberofDiceRollsWithTargetSum %7B%0A  /*%0A  out of f%5Ed total ways.%0A  Return the number of possible ways%0A  modulo 10%5E9 + 7 to roll the dice so%0A  the sum of the face-up numbers equals target.%0A%0A  1 %3C= d, f %3C= 30%0A  1 %3C= target %3C= 1000%0A%0A  Input: d = 1, f = 6, target = 3%0A  Output: 1%0A%0A  Input: d = 2, f = 6, target = 7%0A  Output: 6%0A%0A  Input: d = 2, f = 5, target = 10%0A  Output: 1%0A%0A  Input: d = 1, f = 2, target = 3%0A  Output: 0%0A%0A  Input: d = 30, f = 30, target = 500%0A  Output: 222616187%0A%0A  Idea: each dice will take part in.%0A  O(f %5E d) runtime.%0A  O(d) space for the stack.%0A  */%0A%0A  private Map%3CString, Integer%3E cache = new HashMap();%0A%0A  int numRollsToTarget(int dice, int face, int target) %7B%0A    if (dice == 0 && target == 0) return 1;%0A    if (dice == 0 %7C%7C target %3C= 0) return 0;%0A    String k = dice + %22-%22 + target;%0A    if (cache.containsKey(k)) return cache.get(k);%0A    int sum = 0;%0A    for (int f = 1; f %3C= face; f++)%0A      sum = (sum + numRollsToTarget(dice - 1, face, target - f)) %25 1000000007;%0A    cache.put(k, sum);%0A    return sum;%0A  %7D%0A%0A  /*%0A  bottom up%0A  processing dp%5Btarget%5D backwards,%0A  clear the previous dp%5Btarget%5D%0A  O(dice * face * target) time, O(target) space%0A  */%0A  int numRollsToTarget2(int dice, int face, int target) %7B%0A    int%5B%5D dp = new int%5Btarget + 1%5D;%0A    dp%5B0%5D = 1;%0A    for (int d = 1; d %3C= dice; d++) %7B%0A      for (int t = target; t %3E= 0; t--) %7B%0A        dp%5Bt%5D = 0;%0A        for (int pred = t - 1; pred %3E= Math.max(0, t - face); pred--) %7B%0A          dp%5Bt%5D = (dp%5Bt%5D + dp%5Bpred%5D) %25 1000000007;%0A        %7D%0A      %7D%0A    %7D%0A    return dp%5Btarget%5D;%0A  %7D%0A%7D%0A

1155. Number of Dice Rolls With Target Sum