E-找终点(100p)

找终点

问题描述

给定一个正整数数组 ，数组最大长度为 100。你需要从第一个元素开始，计算到达数组最后一个元素所需的最少步数。

移动规则如下：

1. 第一步必须从第一个元素开始，步长范围为 ，其中 为数组长度。
2. 从第二步开始，每一步的步长必须等于当前所在位置的元素值，不能多也不能少。
3. 只能向数组尾部移动，不能往回走。

如果无法到达最后一个元素，则返回 。

输入格式

输入为一行，包含若干个正整数，以空格分隔，表示给定的数组 。数组长度小于 100。

输出格式

输出一个整数，表示最少的步数。如果无法到达最后一个元素，输出 。

样例输入1

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

样例输出1

2

样例输入2

1 2 3 7 1 5 9 3 2 1

样例输出2

-1

样例解释

数据范围

题解

动态规划

这道题目本质上是一个动态规划问题，需要找到从起点到终点的最短路径。一步步来分析这个问题：

1. 首先，需要考虑第一步的特殊性。第一步可以选择的步长范围是 。这意味着我们需要尝试所有可能的第一步，并为每种可能性计算最短路径。

2. 从第二步开始，每一步的步长都是固定的，等于当前位置的元素值。这简化了我们的计算，因为每个位置的下一步是确定的。

3. 我们可以使用一个数组 来存储到达每个位置的最少步数。初始时，除了起点外，所有位置的步数都设为无穷大。

4. 对于第一步，遍历所有可能的步长，更新相应位置的步数为 1。

5. 然后，从前往后遍历数组。对于每个已经可以到达的位置（即 不为无穷大），尝试从这个位置跳到下一个位置。如果能跳到，并且新的步数小于已记录的步数，我们就更新 数组。

6. 最后，检查终点的步数。如果它不是无穷大，说明可以到达，返回这个步数；否则，返回 -1。

参考代码

• Python

def min_steps(nums):
    n = len(nums)
    # 初始化dp数组，除起点外都设为无穷大
    dp = [float('inf')] * n
    dp[0] = 0
    
    # 处理第一步
    for i in range(1, min(n, n // 2)):
        dp[i] = 1
    
    # 动态规划过程
    for i in range(n):
        if dp[i] != float('inf'):
            # 如果当前位置可达，尝试跳到下一个位置
            next_pos = i + nums[i]
            if next_pos < n:
                dp[next_pos] = min(dp[next_pos], dp[i] + 1)
    
    # 返回结果
    return dp[-1] if dp[-1] != float('inf') else -1

# 读取输入
nums = list(map(int, input().split()))

# 计算并输出结果
print(min_steps(nums))

• C

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

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int min_steps(int* nums, int n) {
    // 动态分配dp数组
    int* dp = (int*)malloc(n * sizeof(int));
    // 初始化dp数组，除起点外都设为INT_MAX
    for (int i = 0; i < n; i++) {
        dp[i] = INT_MAX;
    }
    dp[0] = 0;
    
    // 处理第一步
    for (int i = 1; i < n / 2 && i < n; i++) {
        dp[i] = 1;
    }
    
    // 动态规划过程
    for (int i = 0; i < n; i++) {
        if (dp[i] != INT_MAX) {
            // 如果当前位置可达，尝试跳到下一个位置
            int next_pos = i + nums[i];
            if (next_pos < n) {
                dp[next_pos] = MIN(dp[next_pos], dp[i] + 1);
            }
        }
    }
    
    // 保存结果
    int result = (dp[n-1] != INT_MAX) ? dp[n-1] : -1;
    
    // 释放动态分配的内存
    free(