找终点

标题：找终点 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限

给定一个正整数数组，设为nums，最大为100个成员，求从第一个成员开始，正好走到数组最后一个成员，所使用的最少步骤数。

要求：

1、第一步必须从第一元素开始，且1<=第一步的步长<len/2;（len为数组的长度，需要自行解析）。

2、从第二步开始，只能以所在成员的数字走相应的步

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        while (in.hasNextInt()) {
            list.add(in.nextInt());
        }
        System.out.println(getSteps(list));

    }

    public static int getSteps(List<Integer> data) {
        int minSteps = Integer.MAX_VALUE;
        for (int i = 1; i < data.size() / 2; i++) {
            int current = i;
            int steps = 0;
            while (current < data.size() - 1) {
                steps++;
                if (steps == 1) {
                    current = i;
                } else {
                    current += data.get(current);
                }
            }
            if (current == data.size() - 1) {
                if (steps < minSteps) {
                    minSteps = steps;
                }
            }
        }
        if (minSteps == Integer.MAX_VALUE) {
            return -1;
        } else {
            return minSteps;
        }
    }
}

str = input()
strs = str.split(" ")
arr = [int(item) for item in strs]

num = len(arr)
max_int=1<<31
dp =[max_int for i in range(num)]
dp[0] = 0
for i in range(1,int(num/2)):
    dp[i]=1
    
    if(i+arr[i]<num):
        dp[i+arr[i]] = min(2, dp[i+arr[i]])
for i in range(int(num/2),num):
    if(i+arr[i]<num):
        dp[i+arr[i]] = min(dp[i+arr[i]],dp[i]+1)
        
if dp[num-1]==max_int:
    print(-1)
else:
    print(dp[num-1])

#include <stdio.h>
#include <memory.h>
int main()
{
	int data[100] = {0};
	int dp[100] = {0};
	int count = 0;
	int i = 0;
	int pos = 0;
	memset(dp,-1,100*sizeof(int));
	do
	{
		scanf("%d",&data[count]);
		count++;	
	}while(getchar()!='\n');
	for(i = 1;i<count/2;i++)
	{		
		int steps = 1;
		dp[i] = 1;
		pos = i;
		while(pos+data[pos]<count)
		{
			steps++;
			if(dp[pos+data[pos]] == -1)
			{
			   dp[pos+data[pos]] = steps;
			}
			else
			{
				dp[pos+data[pos]] = dp[pos+data[pos]]<steps?dp[pos+data[pos]]:steps;
			}
		    pos=pos+data[pos];
		}	
	}
	printf("%d\n",dp[count-1]);
}