Сложность: hard
Вам даны три целых числа n, m и k. Рассмотрим следующий алгоритм для нахождения максимального элемента в массиве положительных целых чисел:
maximum_value = -1
maximum_index = -1
search_cost = 0
n = arr.length
for (i = 0; i < n; i++){
if (maximum_value < arr[i]){
maximum_value = arr[i]
maximum_index = i
search_cost = search_cost + 1
}
}
return maximum_index
Вам необходимо построить массив arr, который имеет следующие свойства:
arr содержит ровно n целых чисел.
1 <= arr[i] <= m, где (0 <= i < n).
После применения указанного алгоритма к arr, значение search_cost равно k.
Верните количество способов построить массив arr с учетом указанных условий. Так как ответ может быть очень большим, ответ должен быть вычислен по модулю 10^9 + 7.
Пример:
Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]
👨💻 Алгоритм:
1⃣Инициализация и базовые случаи: Инициализируем 3D массив dp размером [n+1][m+1][k+1]. Устанавливаем базовые случаи: dp[n][...][0] = 1.
2⃣Итерация и обновление массива dp: Проходим в обратном порядке по индексам i от n-1 до 0, по maxSoFar от m до 0 и по remain от 0 до k. Для каждого из этих значений обновляем dp массив, используя предыдущие результаты для вычисления текущих значений.
3⃣Возврат результата: Возвращаем значение dp[0][0][k], которое является решением исходной задачи.
😎 Решение:
class Solution:
def numOfArrays(self, n: int, m: int, k: int) -> int:
MOD = 10**9 + 7
dp = [[[0] * (k + 1) for _ in range(m + 1)] for _ in range(n + 1)]
for num in range(m + 1):
dp[n][num][0] = 1
for i in range(n - 1, -1, -1):
for maxSoFar in range(m, -1, -1):
for remain in range(k + 1):
ans = 0
for num in range(1, maxSoFar + 1):
ans = (ans + dp[i + 1][maxSoFar][remain]) % MOD
if remain > 0:
for num in range(maxSoFar + 1, m + 1):
ans = (ans + dp[i + 1][num][remain - 1]) % MOD
dp[i][maxSoFar][remain] = ans
return dp[0][0][k]
Ставь 👍 и забирай 📚 Базу знаний