Задача: 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], которое является решением исходной задачи.

😎 Решение:

var numOfArrays = function(n, m, k) {
    const MOD = 1_000_000_007;
    const dp = Array.from({ length: n + 1 }, () => Array.from({ length: m + 1 }, () => Array(k + 1).fill(0)));

    for (let num = 0; num <= m; num++) {
        dp[n][num][0] = 1;
    }

    for (let i = n - 1; i >= 0; i--) {
        for (let maxSoFar = m; maxSoFar >= 0; maxSoFar--) {
            for (let remain = 0; remain <= k; remain++) {
                let ans = 0;
                for (let num = 1; num <= maxSoFar; num++) {
                    ans = (ans + dp[i + 1][maxSoFar][remain]) % MOD;
                }

                if (remain > 0) {
                    for (let num = maxSoFar + 1; num <= m; num++) {
                        ans = (ans + dp[i + 1][num][remain - 1]) % MOD;
                    }
                }

                dp[i][maxSoFar][remain] = ans;
            }
        }
    }

    return dp[0][0][k];
};

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