격자【DP】 점프

▶Description 그들은 공터에 와서 N개의 연속된 네모를 그렸다. 각 네모마다 랜덤으로 숫자를 채웠다. 모두들 첫 번째 칸부터 시작하여 매번 현재 칸의 수를 초과하지 않고 뒤로 뛸 수 있다. 모두들 이 경기를 시작하여 누가 가장 뒤에 있는 칸의 걸음수가 가장 적은지 보자.
> Input 입력 첫 번째 행에는 그리는 칸의 개수를 나타내는 정수 N이 포함됩니다.두 번째 줄은 각 칸의 수ai를 나타내는 N 정수를 포함한다.
>Output에서 한 줄을 출력하여 점프의 최소 수를 나타냅니다.
>Sample Input 5 2 3 1 1 1
>Sample Output 2
40%의 데이터가 N<=10, ai<=10을 충족합니다.100% 데이터에는 N<=5000, ai<=1000이 충족됩니다.
문제풀이 직접 DP:f[i]=i칸까지의 최소 걸음
> 코드

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,a,f[5005];
int main()
{
	memset(f,0x7f,sizeof(f));
	scanf("%d",&n);
	f[1]=0; //   
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		for(int j=i+1;j<=i+a;j++)
		{
		    if(j>n) break; //        
			f[j]=min(f[j],f[i]+1); //      
			if(j==n) //       
			{
				printf("%d",f[n]);
				return 0;
			}
		}
	}
	printf("%d",f[n]);
	return 0;
}