1155.number-of-dice-rolls-with-target-sum.md

title: leetcode 题解之【1155】掷骰子的 N 种方法 date: 2019-08-12 categories: 算法

---

这里有  d  个一样的骰子，每个骰子上都有  f  个面，分别标号为  1, 2, ..., f。

我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。

如果需要掷出的总点数为  target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 f^d 种），模  10^9 + 7  后返回。

题目来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/number-of-dice-rolls-with-target-sum

分析

如果使用回溯法，算法复杂度为 O(f^d)，显然超时

考虑到，投掷 N 个骰子的点数和 = N-1 个骰子的点数和 + 第 N 个骰子的点数

故采用动态规划的方法，定义 dp[i][j]为投掷 i 个骰子，点数和为 j 的方法总数，

可以得到动态转换方程如下

dp[i][j] = dp[i-1][target - 1] + dp[i-1][target - 2] + dp[i-1][target - 3] + ... + dp[i-1][target - f]

以 f=6 为例, dp[i][j]的求解过程

代码实现

递归方式

var numRollsToTarget = function (d, f, target) {
  let MOD = 10 ^ (9 + 7);

  function dp(d, target) {
    if (target <= 0) {
      return 0;
    }
    if (d === 1) {
      return target <= f ? 1 : 0;
    } else if (d > target || d * f < target) {
      return 0;
    } else if (d === target || d * f === target) {
      return 1;
    }
    let count = 0;
    for (let i = 1; i <= f; i++) {
      count += dp(d - 1, target - i);
      count %= MOD;
    }

    return count;
  }

  return dp(d, target);
};

输入：d = 30, f = 30, target = 500 输出：222616187

执行上面的 case 内存溢出，运行超时，下面使用非递归方式优化

使用非递归方式实现

/**
 * @param {number} d
 * @param {number} f
 * @param {number} target
 * @return {number}
 */
var numRollsToTarget = function (d, f, target) {
  if (d === 1) {
    return target <= f ? 1 : 0;
  }

  let MOD = 1000000007;
  let dp = new Array(d + 1);
  for (let i = 0; i < dp.length; i++) {
    dp[i] = new Array(target + 1).fill(0);
  }

  for (let i = 1; i <= f; i++) {
    dp[1][i] = 1;
  }

  for (let i = 2; i <= d; i++) {
    for (let j = i; j <= target && j <= d * f; j++) {
      for (let k = 1; k <= f && j >= k; k++) {
        dp[i][j] += dp[i - 1][j - k];
        dp[i][j] = dp[i][j] % MOD;
      }
    }
  }
  return dp[d][target];
};

执行通过