Number of ways to cut a stick of length N into in even length at most K units long pieces | Recursive function to count the total number of ways ; Base case if no - solution exist ; Condition if a solution exist ; Check if already calculated ; Initialize counter ; Recursive call ; Store the answer ; Return the answer ; Driver code
def solve ( n , k , mod , dp ) : NEW_LINE INDENT if ( n < 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( n == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( dp [ n ] != - 1 ) : NEW_LINE INDENT return dp [ n ] NEW_LINE DEDENT cnt = 0 NEW_LINE for i in range ( 2 , k + 1 , 2 ) : NEW_LINE INDENT cnt = ( ( cnt % mod + solve ( n - i , k , mod , dp ) % mod ) % mod ) NEW_LINE DEDENT dp [ n ] = cnt NEW_LINE return int ( cnt ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mod = 1e9 + 7 NEW_LINE n = 4 NEW_LINE k = 2 NEW_LINE dp = [ - 1 ] * ( n + 1 ) NEW_LINE ans = solve ( n , k , mod , dp ) NEW_LINE print ( ans ) NEW_LINE DEDENT