Count of Arrays of size N having absolute difference between adjacent elements at most 1 | C ++ program of the above approach ; Function to find the count of possible arrays such that the absolute difference between any adjacent elements is atmost 1 ; Stores the dp states where dp [ i ] [ j ] represents count of arrays of length i + 1 having their last element as j ; Case where 1 st array element is missing ; All integers in range [ 1 , M ] are reachable ; Only reachable integer is arr [ 0 ] ; Iterate through all values of i ; If arr [ i ] is not missing ; Only valid value of j is arr [ i ] ; If arr [ i ] is missing ; Iterate through all possible values of j in range [ 1 , M ] ; Stores the count of valid arrays ; Calculate the total count of valid arrays ; Return answer ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countArray ( int arr [ ] , int N , int M ) { int dp [ N ] [ M + 2 ] ; memset ( dp , 0 , sizeof dp ) ; if ( arr [ 0 ] == -1 ) { for ( int j = 1 ; j <= M ; j ++ ) { dp [ 0 ] [ j ] = 1 ; } } else { dp [ 0 ] [ arr [ 0 ] ] = 1 ; } for ( int i = 1 ; i < N ; i ++ ) { if ( arr [ i ] != -1 ) { int j = arr [ i ] ; dp [ i ] [ j ] += dp [ i - 1 ] [ j - 1 ] + dp [ i - 1 ] [ j ] + dp [ i - 1 ] [ j + 1 ] ; } if ( arr [ i ] == -1 ) { for ( int j = 1 ; j <= M ; j ++ ) { dp [ i ] [ j ] += dp [ i - 1 ] [ j - 1 ] + dp [ i - 1 ] [ j ] + dp [ i - 1 ] [ j + 1 ] ; } } } int arrCount = 0 ; for ( int j = 1 ; j <= M ; j ++ ) { arrCount += dp [ N - 1 ] [ j ] ; } return arrCount ; } int main ( ) { int arr [ ] = { 4 , -1 , 2 , 1 , -1 , -1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int M = 10 ; cout << countArray ( arr , N , M ) ; return 0 ; }