题目描述

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

1. 第一步必须从第一元素开始，且 1 <= 第一步的步长 < len/2 (len为数组的长度，需要自行解析)

2. 从第二步开始，只能以所在成员的数字走相应的步数，不能多也不能少,如果目标不可达返回 -1，只输出最少的步骤数量

3. 只能向数组的尾部走，不能往回走。

输入描述

由正整数组成的数组，以空格分隔，数组长度小于100，请自行解析数据数量。

输出描述

正整数，表示最少的步数，如果不存在输出 -1

示例1

输入

7 5 9 4 2 6 8 3 5 4 3 9

输出

2

说明

第一步:第一个可选步长选择2，从第一个成员7开始走2步，到达9;第二步:从9开始，经过自身数字9对应的9个成员到最后，

示例2

输入

1 2 3 7 1 5 9 3 2 1

输出

-1

解题思路

如果最后一脚 迈到终点 则说明该这一步的起脚点 下标 + 对应的值恰好是终点的坐标 如果该点视为终点，逻辑依然成立

递归该逻辑，如果起点落在数组的前半部分，则第一步迈到这里即可以按规则迈到终点

源码 Java

public class StepTo {

	static Input input;
	static {
		input = new Input("7 5 9 4 2 6 8 3 5 4 3 9");
		input = new Input("1 2 3 7 1 5 9 3 2 1");
	}
	public static void main(String[] args) {
		int steps = 1000;
		String[] split = input.nextLine().split(" ");
		int[] array = new int[split.length];

		for (int i = 0; i < split.length; i++) {
			array[i] = Integer.parseInt(split[i]);
		}

		// 如果最后一脚 迈到终点 则说明该这一步的起脚点 下标 + 对应的之恰好是中调的坐标
		// 依次递归个逻辑即可找到路径 计算该路径的步数即可
		for (int i = array.length - 2; i > 0; i--) {
			if (array[i] + i == array.length - 1) {
				int steps1 = getSteps(array, i);
				if (steps1 > 0) {
					steps = Math.min(steps, i);
				}
			}
		}
		if (steps == 1000) {
			System.out.println(-1);
		} else {
			System.out.println(steps);
		}

	}

	public static int getSteps(int[] array, int step) {
		// 如果这一步落在数组的前半部分， 第一步迈到这里即可以到达终点
		if ( step >= 1 && step < (array.length - 1)/2) {
			return 2;
		}
		// 如果起脚点小于 1 说明没有合适的起脚点
		if (step < 1) {
			return -1000;
		}
		int nextStep = -1000;
		// 找到上一脚的起脚点
		for (int i = step - 1; i > 0; i--) {
			if (array[i] + i == step) {
				nextStep = i;
			}
		}
		return  getSteps(array, nextStep) + 1;
	}
}