Количество неубывающих массивов с i-м элементом в диапазоне [A[i], B[i]]
Имея два массива A[] и B[] , каждый из которых состоит из N целых чисел, задача состоит в том, чтобы найти количество неубывающих массивов размера N , которые можно составить так, чтобы каждый элемент массива лежал в диапазоне [A[i], Б[и]] .
Примеры:
Input: A[] = {1, 1}, B[] = {2, 3}
Output: 5
Explanation:
The total number of valid arrays are {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}. Therefore, the count of such arrays is 5.Input: A[] = {3, 4, 5}, B[] = {4, 5, 6}
Output: 8
Подход: Данную проблему можно решить с помощью динамического программирования и суммы префиксов. Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте 2D-массив dp[][] со значениями 0 , где dp[i][j] обозначает общий допустимый массив до позиции i и с текущим элементом как j . Инициализируйте dp[0][0] как 1 .
- Инициализируйте 2D-массив pref[][] со значениями 0 , чтобы сохранить сумму префиксов массива.
- Переберите диапазон [0, B[N – 1]] , используя переменную i , и установите значение pref[0][i] равным 1 .
- Переберите диапазон [1, N], используя переменную i , и выполните следующие шаги:
- Перебрать диапазон [A[i – 1], B[i – 1]] с помощью переменной j и увеличить значение dp[i][j] на pref[i – 1][j] и увеличить значение pref[i][j] от dp[i][j] .
- Перебрать диапазон [0, B[N – 1]] , используя переменную j , и, если j больше 0 , обновить таблицу сумм префиксов, увеличив значение pref[i][j] на pref[i][j] – 1] .
- Инициализируйте переменную ans как 0 , чтобы сохранить результирующее количество сформированных массивов.
- Переберите диапазон [A[N – 1], B[N – 1]] , используя переменную i , и добавьте значение dp[N][i] к переменной ans .
- После выполнения вышеуказанных шагов выведите значение ans в качестве ответа.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N*M), где M — последний элемент массива B[].
Вспомогательное пространство: O(N*M), где M — последний элемент массива B[].