Count the number of ways to divide N in k groups incrementally | DP Table ; Function to count the number of ways to divide the number N in groups such that each group has K number of elements ; Base Case ; if N is divides completely into less than k groups ; If the subproblem has been solved , use the value ; put all possible values greater equal to prev ; Function to count the number of ways to divide the number N in groups ; Initialize DP Table as - 1 ; Driver Code
dp = [ [ [ 0 for i in range ( 50 ) ] for j in range ( 50 ) ] for j in range ( 50 ) ] NEW_LINE def calculate ( pos , prev , left , k ) : NEW_LINE INDENT if ( pos == k ) : NEW_LINE INDENT if ( left == 0 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT else : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT DEDENT if ( left == 0 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( dp [ pos ] [ prev ] [ left ] != - 1 ) : NEW_LINE INDENT return dp [ pos ] [ prev ] [ left ] ; NEW_LINE DEDENT answer = 0 ; NEW_LINE for i in range ( prev , left + 1 ) : NEW_LINE INDENT answer += calculate ( pos + 1 , i , left - i , k ) ; NEW_LINE DEDENT dp [ pos ] [ prev ] [ left ] = answer ; NEW_LINE return dp [ pos ] [ prev ] [ left ] ; NEW_LINE DEDENT def countWaystoDivide ( n , k ) : NEW_LINE INDENT for i in range ( 50 ) : NEW_LINE INDENT for j in range ( 50 ) : NEW_LINE INDENT for l in range ( 50 ) : NEW_LINE INDENT dp [ i ] [ j ] [ l ] = - 1 ; NEW_LINE DEDENT DEDENT DEDENT return calculate ( 0 , 1 , n , k ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 8 ; NEW_LINE K = 4 ; NEW_LINE print ( countWaystoDivide ( N , K ) ) ; NEW_LINE DEDENT