Count possible splits of sum N into K integers such that the minimum is at least P | Function that finds the value of the Binomial Coefficient C ( n , k ) ; Stores the value of Binomial Coefficient in bottom up manner ; Base Case ; Find the value using previously stored values ; Return the value of C ( N , K ) ; Function that count the number of ways to divide N into K integers >= P such that their sum is N ; Update the value of N ; Find the binomial coefficient recursively ; Given K , N , and P
def binomialCoeff ( n , k ) : NEW_LINE INDENT C = [ [ 0 for x in range ( k + 1 ) ] for y in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( min ( i , k ) + 1 ) : NEW_LINE INDENT if ( j == 0 or j == i ) : NEW_LINE INDENT C [ i ] [ j ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT C [ i ] [ j ] = ( C [ i - 1 ] [ j - 1 ] + C [ i - 1 ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT return C [ n ] [ k ] NEW_LINE DEDENT def waysToSplitN ( k , n , P ) : NEW_LINE INDENT new_N = n - k * P NEW_LINE return binomialCoeff ( new_N + k - 1 , new_N ) NEW_LINE DEDENT K = 3 NEW_LINE N = 8 NEW_LINE P = 2 NEW_LINE print ( waysToSplitN ( K , N , P ) ) NEW_LINE