while True:
    try:
        n=int(input().strip())
        num_list=list(map(int,input().split(' ')))
        #print(num_list)
        dp=[]
        infinit=float('inf')
        dp=[infinit for i in range(n+1)]
        #print(dp)
        dp[0]=0
        for i in range(1,n+1):
            for j in range(i):
                if num_list[j]+j>=i:#运用动态规划，如果num_list[j]+j>=i表示可以调到i处
                    dp[i]=min(dp[i],dp[j]+1)#因此需要与dp[i]处的原值进行比较，dp[j]+1表示dp[j]处的值再跳一次
        if dp[n-1]!=infinit:
            print(dp[n])
        else:
            print(-1)
    except:
        break

inf=float('inf')
a,b=int(input()),list(map(int,input().split()))
N=10000
dp=[inf for i in range(N+1)]
dp[0]=0
for i in range(1,a+1):
    for j in range(i):
        if b[j]+j>=i:
            dp[i]=min(dp[i],dp[j]+1)
print(-1 if dp[a]==inf else dp[a])

def jump(l):
    ans = []
    l_reverse = l[::-1]
    for i, value in enumerate(l_reverse):
        if i == 0:
            ans.append(1)
        else:
            if value == 0:
                ans.append(100001)
            elif value > i: 
# 如果某个位置已经可以跳过对岸，该位置步数为1  (囧，题目说跳到最后一个木桩算过，开始以为一定要跳到最后一个木桩，实际只要跳过对岸即可。)
                ans.append(1)
            else:
                ans.append(min(ans[i - value:i]) + 1)
    return ans

if __name__ == '__main__':
    N = input()
    l = [int(i) for i in input().split(' ')]
    ans = jump(l)
    if ans[-1] > 10000:
        print(-1)
    else:
        print(ans[-1])


'''
动态规划，从后往前计算该位置跳过对岸所需最少步数
'''

典型动态规划问题。

N=int(input())
num=list(map(int,input().split()))
mindp=[0,]#第一个桩的最小跳一定是0次
for i in range(1,N+1):#初始化每个桩的最小跳次数
    mindp.append(10001)
for i in range(1,N+1):#依次计算跳到每个桩需要的最小跳次数
    for j in range(1,i+1):#遍历前面所有的桩，找到一个可以跳到当前桩的位置
        if num[i-j]==0:#如果弹力为零，则当前树桩无用，继续下一个
            continue
        if (i-j)+num[i-j]>=i:
            mindp[i]=min(mindp[i],mindp[i-j]+1)
if mindp[N]==10001:#统计完所有树桩的最小跳次数后，输出结果
    print(-1)
else:
    print(mindp[N])

常规DP，注意题目的坑，要越过最后一个柱子，所以注意一下：

```
import sys
N = int(input())
list_x = [int(x) for x in input().split()]
ans = [0 for i in range(N+1)]
ans[0] = 1 
for i in range(1,N+1): 
    if i!=N: #处理最后一步的特殊情况  
        if list_x[i]==0: 
            continue
    temp_ans = [] 
    for j in range(i): 
        if ans[j]==0: 
            continue 
        if list_x[j]+j>=i:
            temp_ans.append(ans[j]+1)
    if len(temp_ans)!=0:
        ans[i] = min(temp_ans) 
print(ans[-1]-1)

```

def short_path(spring):     distance=len(spring)     if distance==0:         return 0     if spring[0]<1:         return -1     if distance<=1:         return 1     else:         res_list=[]         for i in range(distance):             if distance-i<=spring[i]:                 res = short_path(spring[:i])                 if res >= 0:                     res_list.append(res+1)         return min(res_list) if res_list else -1 def veryshort_path(t_list):     L = len(t_list)     if t_list[0]<=0:         return -1     else:                  res=[0] + [L+1]*L         for i in range(L):                              for j in range(i):                 if t_list[j]>=i-j and res[j]+1<res[i]:                     res[i]=res[j]+1                          if t_list[i]>=len(t_list)-i:                 res[-1] = res[i]+1                 return res[-1] if res[-1] <= L else -1         return res[-1] if res[-1] <= L else -1 # spring = [2,0,1,1,1,1,2] putin1=input('') putin2=input('') spring = [int(x) for x in putin2.split(' ')] # print(spring) print(veryshort_path(spring))

python solution:

这道题把leetcode上的jump game I和jump game II结合起来了。解法如下，时间复杂度为O(n)

def canJump(A):
    jump=[0]
    for i in range(1,a):
        jump.append(max(jump[-1],A[i-1])-1)
        if jump[-1]<0:
            return False
    return True

a,b=int(input()),list(map(int,input().split()))

jump,curEnd,curFurthest=0,0,0
for i in range(a):
    curFurthest=max(curFurthest,i+b[i])
    if curEnd==i:
        jump+=1
        curEnd=curFurthest
print(jump if canJump(b) else -1)

n = int(input())
nums = list(map(int, input().split()))
dp = [0xfffffff]*n
for i in range(n-1, -1, -1):
    for j in range(1, nums[i]+1):
        dp[i] = min(dp[i], dp[i+j]+1 if i+j<n else 1)
print(dp[0] if dp[0]<0xfffffff else -1)

if __name__ == '__main__':
    N = int(input())
    nums = [int(x) for x in input().split()]

    inf = float('inf')
    dp = [inf for j in range(N+1)]  # 跳到第i个木桩需要的最少次数
    dp[0] = 0  # 第0个木桩需要跳0次
    for i in range(N):
        j = 1
        # 跳 j 步会跳到i+j，需要跳dp[i]+1次，不要跳出去
        while j <= nums[i] and i+j <= N:
            dp[i+j] = min(dp[i+j], dp[i]+1)
            j += 1
    print(dp[N] if dp[N] < inf else -1)