Задача: 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons
Сложность: 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 {
    func numOfArrays(_ n: Int, _ m: Int, _ k: Int) -> Int {
        let MOD = 1_000_000_007
        var dp = Array(repeating: Array(repeating: Array(repeating: 0, count: k + 1), count: m + 1), count: n + 1)
        
        for num in 0...m {
            dp[n][num][0] = 1
        }
        
        for i in stride(from: n - 1, through: 0, by: -1) {
            for maxSoFar in stride(from: m, through: 0, by: -1) {
                for remain in 0...k {
                    var ans = 0
                    for num in 1...maxSoFar {
                        ans = (ans + dp[i + 1][maxSoFar][remain]) % MOD
                    }
                    
                    if remain > 0 {
                        for num in (maxSoFar + 1)...m {
                            ans = (ans + dp[i + 1][num][remain - 1]) % MOD
                        }
                    }
                    
                    dp[i][maxSoFar][remain] = ans
                }
            }
        }
        
        return dp[0][0][k]
    }
}

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