|
| 1 | +/* Top Down Method |
| 2 | +-----------------------------------*/ |
1 | 3 | classSolution { |
2 | | - |
3 | | -intmod =1000000007; |
| 4 | +intMOD = (int)1e9 +7; |
| 5 | +Map<String,Integer>memo; |
4 | 6 |
|
5 | 7 | publicintnumRollsToTarget(intn,intk,inttarget) { |
6 | | -if (target >n *k ||target <n)return0; |
7 | | -if (n ==1)returntarget <n ?0 :1; |
8 | | -int[][]dp =newint[n +1][target +1]; |
9 | | -returnhelper(n,k,target,dp); |
| 8 | +memo =newHashMap<>(); |
| 9 | +returncount(n,k,target); |
| 10 | + } |
| 11 | + |
| 12 | +privateintcount(intn,intk,inttarget){ |
| 13 | +StringcurrState =n +"," +target; |
| 14 | +if(n ==0) |
| 15 | +return (target ==0)?1:0; |
| 16 | +if(memo.containsKey(currState)) |
| 17 | +returnmemo.get(currState); |
| 18 | + |
| 19 | +intres =0; |
| 20 | +for(intval =1;val <k +1;val++) |
| 21 | +res = (res +count(n -1,k,target -val)) %MOD; |
| 22 | +memo.put(currState,res); |
| 23 | +returnres; |
10 | 24 | } |
| 25 | +} |
| 26 | + |
| 27 | +/* Bottom Up Method |
| 28 | +-----------------------------------------*/ |
| 29 | +classSolution { |
| 30 | +publicintnumRollsToTarget(intn,intk,inttarget) { |
| 31 | +int[]dp =newint[target +1]; |
| 32 | +dp[0] =1; |
| 33 | +intMOD = (int)1e9 +7; |
| 34 | + |
| 35 | +for(intdice =0;dice <n;dice++){ |
| 36 | +int[]next_dp =newint[target +1]; |
11 | 37 |
|
12 | | -publicinthelper(intn,intk,inttarget,int[][]dp) { |
13 | | -if (target >n *k ||target <n)return0; |
14 | | -if (target ==0 &&n ==0)return1; |
15 | | -if (dp[n][target] !=0)returndp[n][target]; |
16 | | -intsum =0; |
17 | | -for (inti =1;i <=k;i++) { |
18 | | -sum = (sum +helper(n -1,k,target -i,dp)) %mod; |
| 38 | +for(intval =1;val <k +1;val++){ |
| 39 | +for(inttotal =val;total <target +1;total++){ |
| 40 | +next_dp[total] = (next_dp[total] +dp[total -val]) %MOD; |
| 41 | + } |
| 42 | + } |
| 43 | +dp =next_dp; |
19 | 44 | } |
20 | | -returndp[n][target] =sum; |
| 45 | +returndp[target]; |
21 | 46 | } |
22 | 47 | } |