1155-掷骰子等于目标和的方法数

这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。

给定三个整数 n , k 和 target ，返回可能的方式(从总共 _ _kn _ _
种方式中)滚动骰子的数量，使正面朝上的数字之和等于 _ _target 。

答案可能很大，你需要对 109 + 7 取模。

示例 1：

**输入：** n = 1, k = 6, target = 3
**输出：** 1
**解释：** 你扔一个有 6 个面的骰子。
得到 3 的和只有一种方法。

示例 2：

**输入：** n = 2, k = 6, target = 7
**输出：** 6
**解释：** 你扔两个骰子，每个骰子有 6 个面。
得到 7 的和有 6 种方法：1+6 2+5 3+4 4+3 5+2 6+1。

示例 3：

**输入：** n = 30, k = 30, target = 500
**输出：** 222616187
**解释：** 返回的结果必须是对 109 + 7 取模。

提示：

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

解题思路：

步骤一：类似于求路径总和，如果用 bracktrack，时间复杂度 O(f ^ d)，不靠谱啊。果断套 DP。
步骤二：求状态转移方程 (STE)：
- 状态：dp[i][j] 代表扔 i 个骰子和为 j；
- 方程：dp[i][j] 与 dp[i - 1] 的关系是什么呢？第 i 次我投了 k ( 1 <= k <= f)，那么前 i - 1 次和为 j - k，对应 dp[i - 1][j - k]；
  于是有最终方程：dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j - 2] + ... + dp[i - 1][j - f]
- 边界条件： dp[1][k] = 1 ( 1<= k <= min(target, f) )

代码：

[ ]private static final int MOD = 1000000007;
public int numRollsToTarget(int d, int f, int target) {
  int[][] dp = new int[31][1001];
  int min = Math.min(f, target);
  for (int i = 1; i <= min; i++) {
    dp[1][i] = 1;
  }
  int targetMax = d * f;
  for (int i = 2; i <= d; i++) {
    for (int j = i; j <= targetMax; j++) {
      for (int k = 1; j - k >= 0 && k <= f; k++) {
        dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
      }
    }
  }
  return dp[d][target];
}

关于为什么取模 1e9 + 7：

简单来说就是：

取模防止大数运算出现 overflow
为什么取 1e9 + 7 等 prime number 记为 P，可以减少实际答案 A mapping 到 A mod P 的碰撞率。我们约定认为，如果你 A mod P 如果是对的，那么你算出的 A 也是对的。
还有就是，对于参赛选手来说，这个数好记，不容易出现手误之类的；

更详细的 digging 看下面的链接：

关于有些童鞋问为什么不最后取模的解释：

还是举个例子吧，input 设为 d = 30, f = 30, target=500，然后我们写段测试代码：

[]System.out.println(String.format("Int Max: %s", Integer.MAX_VALUE));
long sum = 0;
for (int i : dp[d - 1]) {
  sum += i;
}
System.out.println(String.format("dp[d - 1] sum: %s", sum));
System.out.println(String.format("dp[d - 1]: %s", Arrays.toString(dp[d - 1])));

具体的 OUTPUT 看我最后面给的数据。

可以看到，在你最后一步取模之前，早就 Overflow。在我题解里给的 refs Modulo 10^9+7 (1000000007) 里面有个 mod 的加法性质：最后取模等效于步步取模 (A + B) mod M = (A mod M + B mod M) mod M。

在理论上你最后取模是成立的，但我们用的计算机则存在风险：你取模之前已经溢出了。而我们在代码里每次迭代都取模，则杜绝了这个风险。另外还可以注意一下，我们是两两相加之后取模的，因为 1000000007 * 2 < Integer.MAX_VALUE ，简化了下。其实我们完全可以写成：dp[i][j] = (dp[i][j] % MOD + dp[i - 1][j - k] % MOD) % MOD。

附上测试代码的 OUTPUT 数据

Int Max: 2147483647
dp[d - 1] sum: 418862669522
dp[d - 1]: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 29, 435, 4495, 35960, 237336, 1344904, 6724520, 30260340, 124403620, 472733756, 676056037, 586853445, 620076241, 860228716, 532655639, 714803002, 68596169, 953079104, 199721979, 679332751, 918443081, 814643357, 67252649, 979047412, 155580500, 861590273, 273609805, 547219610, 144535089, 79434475, 893116446, 799582292, 447605678, 109534627, 392156698, 114845677, 507694681, 290307514, 885793603, 629668714, 37969701, 53907942, 951712368, 854332693, 341219139, 234391554, 697432073, 114681024, 392880267, 307665840, 162345404, 909488304, 847140827, 300076096, 314954988, 254066441, 862081601, 829284290, 686157014, 183655830, 794131720, 626551851, 860830766, 645169812, 706836850, 799085852, 902302371, 77524967, 486121379, 306019009, 30755439, 11326789, 262333265, 142508889, 67677058, 598818525, 756242041, 482755347, 25850332, 270837728, 11408703, 92029246, 658885092, 386666719, 778410728, 319573952, 934722102, 260464715, 104838557, 979827891, 896507297, 399453482, 513197167, 365207666, 65408661, 564073391, 734555732, 130214580, 697786154, 197871237, 256360874, 725194355, 977001461, 163452532, 288002316, 801613502, 837514549, 419709827, 866008819, 611321508, 361078669, 274130200, 8495499, 41414194, 152839277, 861563673, 344595413, 147525291, 680144830, 693618995, 15047860, 523465907, 540486275, 924389076, 788399528, 425520524, 365187225, 773070415, 365336170, 147073737, 808135875, 954996399, 295585930, 370950412, 708204907, 821195563, 749340081, 226864069, 679862549, 739507260, 643929348, 853976941, 653425722, 772672340, 64736410, 839770175, 211653702, 809453455, 544599208, 371926533, 214591351, 854660574, 858315710, 731742570, 247343279, 496268936, 762565730, 461788976, 464400254, 16200211, 344216516, 459199184, 18114459, 608129954, 97578284, 338345236, 93736006, 141923650, 239437152, 16657446, 463654541, 754571164, 113053087, 103262985, 614749182, 945862341, 466194470, 912912017, 828312857, 252025671, 565654242, 567083154, 295646539, 202557576, 270278176, 941833338, 843470719, 228674901, 856273780, 515192130, 260784877, 53785843, 517492193, 813531576, 647840140, 167775845, 645868968, 593505316, 353743114, 909474918, 897275524, 655105156, 784923129, 537993088, 195015224, 818582794, 803346103, 900998533, 174321215, 494923073, 863221859, 482791676, 736861123, 709819237, 727562101, 160248311, 590189732, 40643294, 717996182, 536467761, 506324056, 115425139, 939625609, 545416294, 133569583, 917480018, 693845863, 292669224, 696411698, 484474367, 658766053, 447953722, 909804251, 174556714, 297552713, 470528079, 531103582, 328293922, 622427710, 376385029, 89961942, 101002360, 588188675, 315961823, 125555359, 394527017, 899822801, 331169575, 94936677, 777127909, 467573120, 627166257, 939700057, 154902021, 749830367, 673334215, 182908835, 187750555, 119269293, 40345845, 857173494, 842111183, 875714316, 340346555, 85779220, 380530955, 122612554, 976112394, 981839153, 919136961, 566211403, 75040820, 979096722, 349021657, 654220621, 534526105, 527741640, 906461181, 862765100, 100410219, 195308148, 2925249, 319843621, 439842237, 941938366, 663433682, 180344971, 614251499, 928383256, 165619436, 103968665, 323380139, 71088087, 118378314, 277016030, 274734219, 882688722, 954753261, 486392596, 992221971, 595041862, 232549341, 320631417, 468946246, 258338068, 827010721, 765814489, 916671870, 467190582, 243685065, 858208593, 818728965, 760618488, 747951315, 471445982, 235600878, 862292990, 838899741, 794321688, 515100713, 572674769, 194736691, 563066404, 644968325, 581977045, 464948418, 452618356, 375597361, 622459286, 972420275, 665595599, 930268056, 559678225, 669699537, 999892709, 654750313, 570566891, 321310143, 378799443, 610235141, 591891306, 511694663, 843387304, 21760772, 413433597, 29138334, 567058549, 741330128, 44569544, 640508049, 982112749, 534880725, 163910981, 559688384, 928540243, 876201316, 333373034, 954620273, 900749356, 119674876, 511646148, 178208672, 954927893, 801344287, 875406499, 784751920, 115841312, 691581188, 569198453, 765604544, 943648297, 868898358, 762195094, 451773089, 887538727, 235000584, 307764172, 206626589, 167155778, 634377871, 809011775, 156706429, 770812115, 939489442, 312673135, 348056372, 923464253, 259660047, 231560181, 948510661, 824965969, 718229212, 225414788, 218528842, 943287710, 376597255, 744440338, 575041736, 254366659, 176820821, 517644324, 48234764, 356058442, 134765092, 118517652, 598372952, 476264788, 50965049, 82802812, 918654752, 491802618, 349674341, 166462801, 193276905, 593546681, 657823058, 774733041, 290975026, 931530770, 549299692, 549299692, 931530770, 290975026, 774733041, 657823058, 593546681, 193276905, 166462801, 349674341, 491802618, 918654752, 82802812, 50965049, 476264788, 598372952, 118517652, 134765092, 356058442, 48234764, 517644324, 176820821, 254366659, 575041736, 744440338, 376597255, 943287710, 218528842, 225414788, 718229212, 824965969, 948510661, 231560181, 259660047, 923464253, 348056372, 312673135, 939489442, 770812115, 156706429, 809011775, 634377871, 167155778, 206626589, 307764172, 235000584, 887538727, 451773089, 762195094, 868898358, 943648297, 765604544, 569198453, 691581188, 115841312, 784751920, 875406499, 801344287, 954927893, 178208672, 511646148, 119674876, 900749356, 954620273, 333373034, 876201316, 928540243, 559688384, 163910981, 534880725, 982112749, 640508049, 44569544, 741330128, 567058549, 29138334, 413433597, 21760772, 843387304, 511694663, 591891306, 610235141, 378799443, 321310143, 570566891, 654750313, 999892709, 669699537, 559678225, 930268056, 665595599, 972420275, 622459286, 375597361, 452618356, 464948418, 581977045, 644968325, 563066404, 194736691, 572674769, 515100713, 794321688, 838899741, 862292990, 235600878, 471445982, 747951315, 760618488, 818728965, 858208593, 243685065, 467190582, 916671870, 765814489, 827010721, 258338068, 468946246, 320631417, 232549341, 595041862, 992221971, 486392596, 954753261, 882688722, 274734219, 277016030, 118378314, 71088087, 323380139, 103968665, 165619436, 928383256, 614251499, 180344971, 663433682, 941938366, 439842237, 319843621, 2925249, 195308148, 100410219, 862765100, 906461181, 527741640, 534526105, 654220621, 349021657, 979096722, 75040820, 566211403, 919136961, 981839153, 976112394, 122612554, 380530955, 85779220, 340346555, 875714316, 842111183, 857173494, 40345845, 119269293, 187750555, 182908835, 673334215, 749830367, 154902021, 939700057, 627166257, 467573120, 777127909, 94936677, 331169575, 899822801, 394527017, 125555359, 315961823, 588188675, 101002360, 89961942, 376385029, 622427710, 328293922, 531103582, 470528079, 297552713, 174556714, 909804251, 447953722, 658766053, 484474367, 696411698, 292669224, 693845863, 917480018, 133569583, 545416294, 939625609, 115425139, 506324056, 536467761, 717996182, 40643294, 590189732, 160248311, 727562101, 709819237, 736861123, 482791676, 863221859, 494923073, 174321215, 900998533, 803346103, 818582794, 195015224, 537993088, 784923129, 655105156, 897275524, 909474918, 353743114, 593505316, 645868968, 167775845, 647840140, 813531576, 517492193, 53785843, 260784877, 515192130, 856273780, 228674901, 843470719, 941833338, 270278176, 202557576, 295646539, 567083154, 565654242, 252025671, 828312857, 912912017, 466194470, 945862341, 614749182, 103262985, 113053087, 754571164, 463654541, 16657446, 239437152, 141923650, 93736006, 338345236, 97578284, 608129954, 18114459, 459199184, 344216516, 16200211, 464400254, 461788976, 762565730, 496268936, 247343279, 731742570, 858315710, 854660574, 214591351, 371926533, 544599208, 809453455, 211653702, 839770175, 64736410, 772672340, 653425722, 853976941, 643929348, 739507260, 679862549, 226864069, 749340081, 821195563, 708204907, 370950412, 295585930, 954996399, 808135875, 147073737, 365336170, 773070415, 365187225, 425520524, 788399528, 924389076, 540486275, 523465907, 15047860, 693618995, 680144830, 147525291, 344595413, 861563673, 152839277, 41414194, 8495499, 274130200, 361078669, 611321508, 866008819, 419709827, 837514549, 801613502, 288002316, 163452532, 977001461, 725194355, 256360874, 197871237, 697786154, 130214580, 734555732, 564073391, 65408661, 365207666, 513197167, 399453482, 896507297, 979827891, 104838557, 260464715, 934722102, 319573952, 778410728, 386666719, 658885092, 92029246, 11408703, 270837728, 25850332, 482755347, 756242041, 598818525, 67677058, 142508889, 262333265, 11326789, 30755439, 306019009, 486121379, 77524967, 902302371, 799085852, 706836850, 645169812, 860830766, 626551851, 794131720, 183655830, 686157014, 829284290, 862081601, 254066441, 314954988, 300076096, 847140827, 909488304, 162345404, 307665840, 392880267, 114681024, 697432073, 234391554, 341219139, 854332693, 951712368, 53907942, 37969701, 629668714, 885793603, 290307514, 507694681, 114845677, 392156698, 109534627, 447605678, 799582292, 893116446, 79434475, 144535089, 547219610, 273609805, 861590273, 155580500, 979047412, 67252649, 814643357, 918443081, 679332751, 199721979, 953079104, 68596169, 714803002, 532655639, 860228716, 620076241, 586853445, 676056037, 472733756, 124403620, 30260340, 6724520, 1344904, 237336, 35960, 4495, 435, 29, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]