Count of Arrays of size N having absolute difference between adjacent elements at most 1 | 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
def countArray ( arr , N , M ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( M + 2 ) ] for j in range ( N ) ] NEW_LINE if ( arr [ 0 ] == - 1 ) : NEW_LINE INDENT for j in range ( 1 , M + 1 , 1 ) : NEW_LINE INDENT dp [ 0 ] [ j ] = 1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT dp [ 0 ] [ arr [ 0 ] ] = 1 NEW_LINE DEDENT for i in range ( 1 , N , 1 ) : NEW_LINE INDENT if ( arr [ i ] != - 1 ) : NEW_LINE INDENT j = arr [ i ] NEW_LINE dp [ i ] [ j ] += dp [ i - 1 ] [ j - 1 ] + dp [ i - 1 ] [ j ] + dp [ i - 1 ] [ j + 1 ] NEW_LINE DEDENT if ( arr [ i ] == - 1 ) : NEW_LINE INDENT for j in range ( 1 , M + 1 , 1 ) : NEW_LINE INDENT dp [ i ] [ j ] += dp [ i - 1 ] [ j - 1 ] + dp [ i - 1 ] [ j ] + dp [ i - 1 ] [ j + 1 ] NEW_LINE DEDENT DEDENT DEDENT arrCount = 0 NEW_LINE for j in range ( 1 , M + 1 , 1 ) : NEW_LINE INDENT arrCount += dp [ N - 1 ] [ j ] NEW_LINE DEDENT return arrCount NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 4 , - 1 , 2 , 1 , - 1 , - 1 ] NEW_LINE N = len ( arr ) NEW_LINE M = 10 NEW_LINE print ( countArray ( arr , N , M ) ) NEW_LINE DEDENT