human
Count of valid arrays of size P with elements in range [ 1 , N ] having duplicates at least M distance apart | Function to calculate the total number of arrays.
If the size of the array is P.
Check if all elements are used atlease once.
Check if this state is already calculated.
Initialize the result.
Use a number from the list of unused numbers.
There are ' unused ' number of favourable choices.
Use a number from already present number atlease M distance back.
There are ' used ▁ - ▁ M ' number of favourable choices.
Store the result.
Function to solve the problem.
Initialize DP table : dp [ i ] [ j ] [ j ] i : current position / index j : number of used elements k : number of unused elements.
Driver Code"
How can the above be solved in Python?
assistant
#Here is code to count of valid arrays of size P with elements in range [ 1 , N ] having duplicates at least M distance apart and the other steps required.
 def calculate ( position , used , unused , P , M , dp ) :
	if ( position == P ) :
		if unused == 0 :
		return 1
		else :
		return 0
	if ( dp [ position ] [ used ] [ unused ] != - 1 ) :
		return dp [ position ] [ used ] [ unused ]
	result = 0
	if ( unused > 0 ) :
		result += calculate ( position + 1 , used + 1 , unused - 1 , P , M , dp ) * unused
	if ( used > M ) :
		result += calculate ( position + 1 , used , unused , P , M , dp ) * ( used - M )
	dp [ position ] [ used ] [ unused ] = result
	return dp [ position ] [ used ] [ unused ]
def solve ( N , P , M ) :
	dp = [ [ [ - 1 for i in range ( 101 ) ] for i in range ( 101 ) ] for j in range ( 101 ) ]
	return calculate ( 0 , 0 , N , P , M , dp )
if __name__ == ' _ _ main _ _ ' :
	N = 2
	M = 0
	P = 3
	print ( solve ( N , P , M ) )