Count of ways in which N can be represented as sum of Fibonacci numbers without repetition | Python3 program for the above approach ; Function to generate the fibonacci number ; First two number of fibonacci sqequence ; Function to find maximum ways to represent num as the sum of fibonacci number ; Generate the Canonical form of given number ; Reverse the number ; Base condition of dp1 and dp2 ; Iterate from 1 to cnt ; Calculate dp1 [ ] ; Calculate dp2 [ ] ; Return final ans ; Function call to generate the fibonacci numbers ; Given number ; Function call
fib = [ 0 ] * 101 NEW_LINE dp1 = [ 0 ] * 101 NEW_LINE dp2 = [ 0 ] * 101 NEW_LINE v = [ 0 ] * 101 NEW_LINE def fibonacci ( ) : NEW_LINE INDENT fib [ 1 ] = 1 NEW_LINE fib [ 2 ] = 2 NEW_LINE for i in range ( 3 , 87 + 1 ) : NEW_LINE INDENT fib [ i ] = fib [ i - 1 ] + fib [ i - 2 ] NEW_LINE DEDENT DEDENT def find ( num ) : NEW_LINE INDENT cnt = 0 NEW_LINE for i in range ( 87 , 0 , - 1 ) : NEW_LINE INDENT if ( num >= fib [ i ] ) : NEW_LINE INDENT v [ cnt ] = i NEW_LINE cnt += 1 NEW_LINE num -= fib [ i ] NEW_LINE DEDENT DEDENT v [ : : - 1 ] NEW_LINE dp1 [ 0 ] = 1 NEW_LINE dp2 [ 0 ] = ( v [ 0 ] - 1 ) // 2 NEW_LINE for i in range ( 1 , cnt ) : NEW_LINE INDENT dp1 [ i ] = dp1 [ i - 1 ] + dp2 [ i - 1 ] NEW_LINE dp2 [ i ] = ( ( ( v [ i ] - v [ i - 1 ] ) // 2 ) * dp2 [ i - 1 ] + ( ( v [ i ] - v [ i - 1 ] - 1 ) // 2 ) * dp1 [ i - 1 ] ) NEW_LINE DEDENT return dp1 [ cnt - 1 ] + dp2 [ cnt - 1 ] NEW_LINE DEDENT fibonacci ( ) NEW_LINE num = 13 NEW_LINE print ( find ( num ) ) NEW_LINE