Counts Path in an Array | Python3 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
mod = 10 ** 9 + 7 NEW_LINE def ways ( arr , n ) : NEW_LINE INDENT dp = [ 0 ] * ( n + 1 ) NEW_LINE dp [ n - 1 ] = 1 NEW_LINE for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT dp [ i ] = 0 NEW_LINE j = 1 NEW_LINE while ( ( j + i ) < n and j <= arr [ i ] ) : NEW_LINE INDENT dp [ i ] += dp [ i + j ] NEW_LINE dp [ i ] %= mod NEW_LINE j += 1 NEW_LINE DEDENT DEDENT return dp [ 0 ] % mod NEW_LINE DEDENT arr = [ 5 , 3 , 1 , 4 , 3 ] NEW_LINE n = len ( arr ) NEW_LINE print ( ways ( arr , n ) % mod ) NEW_LINE