Count of all subsequences having adjacent elements with different parity | Function to find required subsequences ; Initialise the dp [ ] [ ] with 0. ; If odd element is encountered ; Considering i - th element will be present in the subsequence ; Appending i - th element to all non - empty subsequences ending with even element till ( i - 1 ) th indexes ; Considering ith element will not be present in the subsequence ; Considering i - th element will be present in the subsequence ; Appending i - th element to all non - empty subsequences ending with odd element till ( i - 1 ) th indexes ; Considering ith element will not be present in the subsequence ; Count of all valid subsequences ; Driver code
def validsubsequences ( arr , n ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( 2 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( arr [ i - 1 ] % 2 ) : NEW_LINE INDENT dp [ i ] [ 1 ] += 1 NEW_LINE dp [ i ] [ 1 ] += dp [ i - 1 ] [ 0 ] NEW_LINE dp [ i ] [ 1 ] += dp [ i - 1 ] [ 1 ] NEW_LINE dp [ i ] [ 0 ] += dp [ i - 1 ] [ 0 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ 0 ] += 1 NEW_LINE dp [ i ] [ 0 ] += dp [ i - 1 ] [ 1 ] NEW_LINE dp [ i ] [ 0 ] += dp [ i - 1 ] [ 0 ] NEW_LINE dp [ i ] [ 1 ] += dp [ i - 1 ] [ 1 ] NEW_LINE DEDENT DEDENT return dp [ n ] [ 0 ] + dp [ n ] [ 1 ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 5 , 6 , 9 , 7 ] NEW_LINE n = len ( arr ) NEW_LINE print ( validsubsequences ( arr , n ) ) NEW_LINE DEDENT