We do tower hopping
Haskell, 70 58 bytes
f[]=0
f(0:_)=1/0
f(x:s)=minimum[1+f(drop k$x:s)|k<-[1..x]]
Try it online!
EDIT: -12 bytes thanks to @Esolanging Fruit and the OP for deciding to allow infinity!
Returns Infinity
when there is no solution which makes the solution a lot simpler. Since we can only move forwards f
just looks at the head of the list and drops 1<=k<=x
items from the list and recurs. Then we just add 1 to each solution the recursive calls found and take the minimum. If the head is 0 the result will be infinity (since we cannot move there is no solution). Since 1+Infinity==Infinity
this result will be carried back to the callers. If the list is empty that means we have left the array so we return a cost of 0.
Husk, 9 bytes
Γö→▼Mo₀↓ŀ
Returns Inf
when no solution exists.
Try it online!
Explanation
Husk's default return values come in handy here.
Γö→▼Mo₀↓ŀ Implicit input: a list, say [2,3,1,1]
Γ Deconstruct into head H = 2 and tail T = [3,1,1]
ö and feed them into this function:
ŀ Range from 0 to H-1: [0,1]
Mo For each element in range,
↓ drop that many element from T: [[3,1,1],[1,1]]
₀ and call this function recursively on the result: [1,2]
▼ Take minimum of the results: 2
→ and increment: 3
If the input list is empty, then Γ
cannot deconstruct it, so it returns the default integer value, 0.
If the first element is 0, then the result of Mo₀↓ŀ
is an empty list, on which ▼
returns infinity.
Python 2, 124 bytes
def f(a):
i={0};l=len(a)
for j in range(l):
for q in{0}|i:
if q<l:i|=set(range(q-a[q],q-~a[q]))
if max(i)/l:return-~j
Try it online!
-11 bytes thanks to Mr. Xcoder
-12 bytes thanks to Mr. Xcoder and Rod