Count of ways in which N can be represented as sum of Fibonacci numbers without repetition | Java 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 ; Driver code ; Function call to generate the fibonacci numbers ; Given number ; Function call
import java . util . * ; class GFG { static long [ ] fib = new long [ 101 ] ; static long [ ] dp1 = new long [ 101 ] ; static long [ ] dp2 = new long [ 101 ] ; static long [ ] v = new long [ 101 ] ; static void fibonacci ( ) { fib [ 1 ] = 1 ; fib [ 2 ] = 2 ; for ( int i = 3 ; i <= 87 ; i ++ ) { fib [ i ] = fib [ i - 1 ] + fib [ i - 2 ] ; } } static long find ( int num ) { int cnt = 0 ; for ( int i = 87 ; i > 0 ; i -- ) { if ( num >= fib [ i ] ) { v [ cnt ++ ] = i ; num -= fib [ i ] ; } } for ( int i = 0 ; i < cnt / 2 ; i ++ ) { long t = v [ i ] ; v [ i ] = v [ cnt - i - 1 ] ; v [ cnt - i - 1 ] = t ; } dp1 [ 0 ] = 1 ; dp2 [ 0 ] = ( v [ 0 ] - 1 ) / 2 ; for ( int i = 1 ; i < cnt ; i ++ ) { dp1 [ i ] = dp1 [ i - 1 ] + dp2 [ i - 1 ] ; dp2 [ i ] = ( ( v [ i ] - v [ i - 1 ] ) / 2 ) * dp2 [ i - 1 ] + ( ( v [ i ] - v [ i - 1 ] - 1 ) / 2 ) * dp1 [ i - 1 ] ; } return ( dp1 [ cnt - 1 ] + dp2 [ cnt - 1 ] ) ; } public static void main ( String [ ] args ) { fibonacci ( ) ; int num = 13 ; System . out . print ( find ( num ) ) ; } }