Количество массивов размера N, имеющих абсолютную разницу между соседними элементами не более 1

Учитывая положительное целое число M и массив arr[] размера N и несколько целых чисел, пропущенных в массиве, представленном как -1 , задача состоит в том, чтобы найти количество различных массивов после замены всех -1 элементами в диапазоне [ 1, M] такое, что абсолютная разность между любой парой соседних элементов не превосходит 1 .

Примеры:

Input: arr[] = {2, -1, 2}, M = 5
Output: 3
Explanation:
The arrays that follow the given conditions are {2, 1, 2}, {2, 2, 2} and {2, 3, 2}.

Input: arr[] = {4, -1, 2, 1, -1, -1}, M = 10
Output:  5

Подход: Данная проблема может быть решена с использованием динамического программирования на основе следующих наблюдений:

• Рассмотрим двумерный массив, скажем, dp[][] где dp[i][j] представляет количество допустимых массивов длины i+1 , последний элемент которых равен j .
• Поскольку абсолютная разница между любыми соседними элементами должна быть не более 1 , поэтому для любого целого числа j допустимым смежным целым числом может быть j-1 , j и j+1 . Следовательно, любое состояние dp[i][j] можно вычислить с помощью следующего соотношения:

  dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i-1 ][ j-1 ] + dp[ i-1 ][ j+1 ]

• В случаях, когда arr[i] = -1 , вычислите dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] + dp[i-1][ j+1]) для всех значений j в диапазоне [1, M] .
• В случаях, когда arr[i] != -1 , вычислить dp[i][j] = (dp[i-1][j] + dp[i-1][j-1] + dp[i-1] [j+1]) для j = arr[i] .
• Обратите внимание, что в случаях, когда arr[0] = -1 , все значения в диапазоне [1, M] достижимы как 1 ^-й элемент массива, поэтому инициализируйте dp[0][j] = 1 для всех j в диапазоне [1 , M] в противном случае инициализируйте dp[0][arr[0]] = 1 .
• Требуемый ответ будет суммой всех значений dp[N – 1][j] для всех j в диапазоне [1, M] .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*M)
Вспомогательное пространство: O(N*M)