human
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"
Solution in Python:
assistant
#Here is code to count of all subsequences having adjacent elements with different parity and the other steps required.
 def validsubsequences ( arr , n ) :
	dp = [ [ 0 for i in range ( 2 ) ] for j in range ( n + 1 ) ]
	for i in range ( 1 , n + 1 ) :
		if ( arr [ i - 1 ] % 2 ) :
			dp [ i ] [ 1 ] += 1
			dp [ i ] [ 1 ] += dp [ i - 1 ] [ 0 ]
			dp [ i ] [ 1 ] += dp [ i - 1 ] [ 1 ]
			dp [ i ] [ 0 ] += dp [ i - 1 ] [ 0 ]
		else :
			dp [ i ] [ 0 ] += 1
			dp [ i ] [ 0 ] += dp [ i - 1 ] [ 1 ]
			dp [ i ] [ 0 ] += dp [ i - 1 ] [ 0 ]
			dp [ i ] [ 1 ] += dp [ i - 1 ] [ 1 ]
	return dp [ n ] [ 0 ] + dp [ n ] [ 1 ]
if __name__ == ' _ _ main _ _ ' :
	arr = [ 5 , 6 , 9 , 7 ]
	n = len ( arr )
	print ( validsubsequences ( arr , n ) )