Number of ways to represent a number as sum of k fibonacci numbers | To store fibonacci numbers 42 second number in fibonacci series largest possible integer ; Function to generate fibonacci series ; Recursive function to return the number of ways ; base condition ; for recursive function call ; Driver code
fib = [ 0 ] * 43 NEW_LINE def fibonacci ( ) : NEW_LINE INDENT fib [ 0 ] = 1 NEW_LINE fib [ 1 ] = 2 NEW_LINE for i in range ( 2 , 43 ) : NEW_LINE INDENT fib [ i ] = fib [ i - 1 ] + fib [ i - 2 ] NEW_LINE DEDENT DEDENT def rec ( x , y , last ) : NEW_LINE INDENT if y == 0 : NEW_LINE INDENT if x == 0 : NEW_LINE INDENT return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT Sum , i = 0 , last NEW_LINE while i >= 0 and fib [ i ] * y >= x : NEW_LINE INDENT if fib [ i ] > x : NEW_LINE INDENT i -= 1 NEW_LINE continue NEW_LINE DEDENT Sum += rec ( x - fib [ i ] , y - 1 , i ) NEW_LINE i -= 1 NEW_LINE DEDENT return Sum NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT fibonacci ( ) NEW_LINE n , k = 13 , 3 NEW_LINE print ( " Possible ▁ ways ▁ are : " , rec ( n , k , 42 ) ) NEW_LINE DEDENT