Задача: 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.

😎 Решение:

public class Solution {
    private const int MOD = 1_000_000_007;

    private int WaysToTarget(int[][] memo, int diceIndex, int n, int currSum, int target, int k) {
        if (diceIndex == n) {
            return currSum == target ? 1 : 0;
        }
        if (memo[diceIndex][currSum] != -1) {
            return memo[diceIndex][currSum];
        }

        int ways = 0;
        for (int i = 1; i <= Math.Min(k, target - currSum); i++) {
            ways = (ways + WaysToTarget(memo, diceIndex + 1, n, currSum + i, target, k)) % MOD;
        }
        memo[diceIndex][currSum] = ways;
        return ways;
    }

    public int NumRollsToTarget(int n, int k, int target) {
        int[][] memo = new int[n + 1][];
        for (int i = 0; i <= n; i++) {
            memo[i] = new int[target + 1];
            Array.Fill(memo[i], -1);
        }
        return WaysToTarget(memo, 0, n, 0, target, k);
    }
}

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