Sequences of given length where every element is more than or equal to twice of previous | DP based function to find the number of special sequences ; define T and build in bottom manner to store number of special sequences of length n and maximum value m ; Base case : If length of sequence is 0 or maximum value is 0 , there cannot exist any special sequence ; if length of sequence is more than the maximum value , special sequence cannot exist ; If length of sequence is 1 then the number of special sequences is equal to the maximum value For example with maximum value 2 and length 1 , there can be 2 special sequences { 1 } , { 2 } ; otherwise calculate ; Driver Code
< ? php function getTotalNumberOfSequences ( $ m , $ n ) { $ T = array ( array ( ) ) ; for ( $ i = 0 ; $ i < $ m + 1 ; $ i ++ ) { for ( $ j = 0 ; $ j < $ n + 1 ; $ j ++ ) { if ( $ i == 0 or $ j == 0 ) $ T [ $ i ] [ $ j ] = 0 ; else if ( $ i < $ j ) $ T [ $ i ] [ $ j ] = 0 ; else if ( $ j == 1 ) $ T [ $ i ] [ $ j ] = $ i ; else $ T [ $ i ] [ $ j ] = $ T [ $ i - 1 ] [ $ j ] + $ T [ $ i / 2 ] [ $ j - 1 ] ; } } return $ T [ $ m ] [ $ n ] ; } $ m = 10 ; $ n = 4 ; echo " Total ▁ number ▁ of ▁ possible ▁ sequences ▁ " , getTotalNumberOfSequences ( $ m , $ n ) ; ? >