Сложность: 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:
MOD = 10**9 + 7
def waysToTarget(self, memo, diceIndex, n, currSum, target, k):
if diceIndex == n:
return int(currSum == target)
if memo[diceIndex][currSum] != -1:
return memo[diceIndex][currSum]
ways = 0
for i in range(1, min(k, target - currSum) + 1):
ways = (ways + self.waysToTarget(memo, diceIndex + 1, n, currSum + i, target, k)) % self.MOD
memo[diceIndex][currSum] = ways
return ways
def numRollsToTarget(self, n, k, target):
memo = [[-1] * (target + 1) for _ in range(n + 1)]
return self.waysToTarget(memo, 0, n, 0, target, k)
Ставь 👍 и забирай 📚 Базу знаний