gistfile1.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define SIZE 10000

int array[SIZE] = {0};

int calc(int size, int* array, int* dp, int position)
{
	if(position == size -1)
		return 0;
	if(array[position] == 0)
		return -1;
	if(dp[position] != 0)
		return dp[position];

	int i;
	int min = size;
	int possible = 0;
	for(i = 1; i <= array[position]; i++)
	{
		if(position + i < size)
		{
			int tmp = calc(size, array, dp, position + i);
			if(tmp != -1)
			{
				possible = 1;
				tmp += 1;
				if(tmp < min)
					min = tmp;
			}
		}
	}
	if(possible)
	{
		dp[position] = min;
		return min;
	}
	else
	{
		dp[position] = -1;
		return -1;
	}
}

int walk(int array_size, int* array)
{
	int * dp = (int *) malloc(array_size * sizeof(int));
	memset(dp, 0, array_size * sizeof(int));
	printf("%d\n", calc(array_size, array, dp, 0));
}

int main()
{
	int n;
	scanf("%d", &n);
	int i;
	for(i = 0; i < n; i++)
	{
		scanf("%d", &array[i]);
	}
	walk(n, array);
}