Задача: 1155. Number of Dice Rolls With Target Sum
Сложность: medium

У вас есть n кубиков, и на каждом кубике k граней, пронумерованных от 1 до k.

Даны три целых числа n, k и target. Необходимо вернуть количество возможных способов (из общего количества kn способов) выбросить кубики так, чтобы сумма выпавших чисел равнялась target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.

👨‍💻 Алгоритм:

1⃣Начните с:

Индекс кубика diceIndex равен 0; это индекс кубика, который мы рассматриваем в данный момент.
Сумма чисел на предыдущих кубиках currSum равна 0.
Инициализируйте переменную ways значением 0. Итерируйтесь по значениям от 1 до k для каждого значения i. Если текущий кубик может иметь значение i, т.е. currSum после добавления i не превысит значение target, то обновите значение currSum и рекурсивно перейдите к следующему кубику. Добавьте значение, возвращенное этим рекурсивным вызовом, к ways. Иначе, если это значение невозможно, то выйдите из цикла, так как большие значения также не удовлетворят вышеуказанному условию.

2⃣Базовые случаи:

Если мы перебрали все кубики, т.е. diceIndex = n, то проверьте, равна ли currSum значению target.

3⃣Верните значение ways и также сохраните его в таблице мемоизации memo, соответствующей текущему состоянию, определяемому diceIndex и currSum.

😎 Решение:

class Solution {
    val MOD = 1_000_000_007

    fun waysToTarget(memo: Array<IntArray>, diceIndex: Int, n: Int, currSum: Int, target: Int, k: Int): Int {
        if (diceIndex == n) {
            return if (currSum == target) 1 else 0
        }
        if (memo[diceIndex][currSum] != -1) {
            return memo[diceIndex][currSum]
        }

        var ways = 0
        for (i in 1..minOf(k, target - currSum)) {
            ways = (ways + waysToTarget(memo, diceIndex + 1, n, currSum + i, target, k)) % MOD
        }
        memo[diceIndex][currSum] = ways
        return ways
    }

    fun numRollsToTarget(n: Int, k: Int, target: Int): Int {
        val memo = Array(n + 1) { IntArray(target + 1) { -1 } }
        return waysToTarget(memo, 0, n, 0, target, k)
    }
}

Ставь 👍 и забирай 📚 Базу знаний