Количество действительных массивов размера P с элементами в диапазоне [1, N], имеющими дубликаты на расстоянии не менее M друг от друга.
Перейти к CDN Copy. Учитывая три целых числа N, M и P , задача состоит в том, чтобы найти общее количество допустимых массивов, которые могут быть созданы размером P , каждый элемент которого находится в диапазоне [1, N], так что дубликаты появляются на расстоянии не менее M отдельно.
Пример :
Input: N = 2, M = 0, P = 3
Output: 6
Explanation: All valid arrays are: {1, 2, 1}, {1, 1, 2}, {2, 1, 1}, {2, 2, 1}, {2, 1, 2}, {1, 2, 2}.Input: N = 2, M = 1, P = 4
Output: 2
Explanation: All valid arrays are: {1, 2, 1, 2}, {2, 1, 2, 1}
Подход: проблема может быть решена с помощью динамического программирования,
- Для каждого индекса возможны два варианта: либо мы добавляем уже используемый элемент на расстоянии не менее M друг от друга , либо мы добавляем новый элемент и уменьшаем количество неиспользуемых символов.
- Чтобы справиться с этим, используйте рекурсивное динамическое программирование .
- Для ускорения рекурсивных вызовов используйте мемоизацию , чтобы уже вычисленные состояния не вычислялись повторно.
- Let’s define: dp[i][j][k] as the number of arrays till i-th position in which j unique elements are present and k be number of elements which are not used.
- На каждом этапе есть два варианта:
1. Выберите ранее встречавшиеся элементы, j и k не изменятся, так как количество используемых и неиспользуемых элементов не изменится: dp[i+1][j][k]
2. Выберите элемент, который никогда не использовался, в этом случае количество используемых символов увеличится на 1, а количество неиспользуемых символов уменьшится на 1: dp[i+1][j+1][k-1]
dp[i][j][k] будет суммой двух вышеуказанных шагов, представленных как:
dp[i][j][k] = dp[i+1][j][k] + dp[i+1][j+1][k-1]
- Окончательный ответ будет dp[0][0][N].
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N*M*P) (из-за трех зависимых переменных)
Вспомогательное пространство: O(N*M*P) (размер матрицы DP)