Количество неубывающих массивов arr3[] таких, что arr1[i] <= arr3[i] <= arr2[i]
Даны два массива arr1[] и arr2[] , содержащие N целых чисел в неубывающем порядке, задача состоит в том, чтобы найти количество неубывающих массивов arr3[] длины N , таких что arr1[i] <= arr3[i] < = arr2[i] для всех значений i в диапазоне [0, N) .
Примеры :
Input: arr1[] = {1, 1}, arr2[] = {2, 3}
Output: 5
Explanation: The 5 possible arrays that follow the required conditions are {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}Input: ranges[] = {{-12, 15}, {3, 9}, {-5, -2}, {20, 25}, {16, 20}}
Output: 247
Подход: Данную задачу можно решить с помощью динамического программирования. Рассмотрим двумерный массив dp[][] такой, что dp[i][j] представляет количество массивов длины i , таких что i -й элемент равен j . Инициализируйте все элементы массива dp как 0 и dp[0][0] как 1 . По наблюдению отношение DP вышеуказанной задачи можно сформулировать следующим образом:
dp[i][j] =
Следовательно, используя приведенное выше соотношение, вычислите значение dp[i][j] для каждого i в диапазоне [0, N] и для каждого j в диапазоне [0, M], где M представляет максимальное целое число в обоих данные массивы arr1[] и arr2[] . Следовательно, значение, хранящееся в dp[N][M] , является требуемым ответом.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N * M), где M представляет максимальное значение целых чисел в массиве arr1[] и arr2[].
Вспомогательное пространство: O(N * M)