Counts Path in an Array | Java implementation of above approach ; find the number of ways to reach the end ; dp to store value ; base case ; Bottom up dp structure ; F [ i ] is dependent of F [ i + 1 ] to F [ i + k ] ; Return value of dp [ 0 ] ; Driver code
class GFG { static final int mod = ( int ) ( 1e9 + 7 ) ; static int ways ( int arr [ ] , int n ) { int dp [ ] = new int [ n + 1 ] ; dp [ n - 1 ] = 1 ; for ( int i = n - 2 ; i >= 0 ; i -- ) { dp [ i ] = 0 ; for ( int j = 1 ; ( ( j + i ) < n && j <= arr [ i ] ) ; j ++ ) { dp [ i ] += dp [ i + j ] ; dp [ i ] %= mod ; } } return dp [ 0 ] % mod ; } public static void main ( String [ ] args ) { int arr [ ] = { 5 , 3 , 1 , 4 , 3 } ; int n = arr . length ; System . out . println ( ways ( arr , n ) % mod ) ; } }