Count number of ways to jump to reach end | function to count ways to jump to reach end for each array element ; count_jump [ i ] store number of ways arr [ i ] can reach to the end ; Last element does not require to jump . Count ways to jump for remaining elements ; if the element can directly jump to the end ; add the count of all the elements that can reach to end and arr [ i ] can reach to them ; if element can reach to end then add its count to count_jump [ i ] ; if arr [ i ] cannot reach to the end ; print count_jump for each array element ; Driver Code
< ? php function countWaysToJump ( $ arr , $ n ) { $ count_jump ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ count_jump [ $ i ] = 0 ; for ( $ i = $ n - 2 ; $ i >= 0 ; $ i -- ) { if ( $ arr [ $ i ] >= $ n - $ i - 1 ) $ count_jump [ $ i ] ++ ; for ( $ j = $ i + 1 ; $ j < $ n - 1 && $ j <= $ arr [ $ i ] + $ i ; $ j ++ ) if ( $ count_jump [ $ j ] != -1 ) $ count_jump [ $ i ] += $ count_jump [ $ j ] ; if ( $ count_jump [ $ i ] == 0 ) $ count_jump [ $ i ] = -1 ; } for ( $ i = 0 ; $ i < $ n ; $ i ++ ) echo $ count_jump [ $ i ] . " ▁ " ; } $ arr = array ( 1 , 3 , 5 , 8 , 9 , 1 , 0 , 7 , 6 , 8 , 9 ) ; $ n = count ( $ arr ) ; countWaysToJump ( $ arr , $ n ) ; ? >