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

Number of Dice Rolls With Target Sum

Nov 9, 2020 · 3 min read

Дано d кубиков с f гранями, т.е. каждый из них может дать число от 1 до f. Сколько есть различных вариантов выкинуть кубики так, чтобы получить заданную сумму target?

Ответ нужно вернуть по модулю 1e9 + 7, чтобы не возиться с BigInt и тому подобным

Задача на LeetCode.

Решение #

Сперва несколько примеров, чтобы лучше понять задачу:

d = 1, f = 6, target = 3

У нас есть ровно один обычный кубик (6 граней). Сколько вариантов выкинуть сумму 3? Один кубик — один вариант.

Теперь другой, менее тривиальный, пример.

d = 2, f = 6, target = 7

На этот раз есть два обычных кубика, и следующие варианты: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1. Всего 6 вариантов. Стоит обратить внимание на симметрию.

Всего f^d возможных вариантов выкинуть кубик, может перебрать все варианты и посчитать нужные суммы? Ограничения в задаче 1 <= d, f <= 30, поэтому экспоненциальное решение точно не пройдёт. Перейдём сразу к динамическому программированию.

Как я уже говорил в задаче про робота, в качестве дпшечки обычно берётся ответ на вопрос самой задачи. В данном случае — сколько есть вариантов выбросить d кубиков с суммой target.

Получается квадратная матрица, каждая строка — количество кубиков, а столбец — количество вариантов получить сумму, равную номеру столбца. Проще говоря, dp[d - 1][target - 1] должен дать ответ на вопрос исходной задачи.

Базовый случай — один кубик.

const dp = new Array(d).fill(0).map(
  () => new Array(target).fill(0)
);

for (let t = 1; t <= target; t++) {
  // ровно один вариант,
  // если количество граней позволяет
  // выкинуть нужную сумму
  dp[0][t - 1] = t <= f ? 1 : 0;
}

Далее начинаем заполнять матрицу ряд за рядом, постепенно приближаясь к решению. Какой рекурсивный переход?

Решение для dp[d][t] определяется суммой по всем сторонам (1..f) и количеством кубиков на единицу меньше (d - 1). Если знаем сумму для dp[d - 1][t - k] — всегда можно выкинуть ещё один кубик со значением k, что и приведёт в нужную сумму t.

/**
 * @param {number} d
 * @param {number} f
 * @param {number} target
 * @return {number}
 */
var numRollsToTarget = function(d, f, target) {
  const dp = new Array(d).fill(0).map(
    () => new Array(target).fill(0)
  );
  const MOD = 1e9 + 7;

  for (let t = 1; t <= target; t++) {
    // ровно один вариант,
    // если количество граней позволяет
    // выкинуть нужную сумму
    dp[0][t - 1] = t <= f ? 1 : 0;
  }

  // постепенно заполняем всю матрицу,
  // бежим по всем кубикам и суммам
  for (let y = 1; y < d; y++) {
    for (let x = 0; x < target; x++) {
      // рекурсивный переход,
      // складываем все варианты получить сумму x - k
      // имея количество кубиков на единицу меньше
      dp[y][x] = [...Array(f + 1).keys()].slice(1).reduce(
        (sum, k) => {
          // нельзя выкинуть отрицательную сумму,
          // соответственно это «ноль вариантов»,
          // по сути ещё один базовый случай
          if (x - k < 0) {
            return sum;
          }
          return (sum + dp[y - 1][x - k]) % MOD;
        }, 0);
    }
  }
  return dp[d - 1][target - 1];
};

PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

Подписывайтесь на мой твитер или канал в телеграме, чтобы узнавать о новых разборах задач.