编辑代码

import java.util.*;

public class DronePathPlanner {
    
    public static int minRelayStations(int[] stations, int D) {
        int n = stations.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0; // 从起点到第一个站点的最少中继站点数是0
        
        for (int i = 0; i < n; i++) {
            if (dp[i] == Integer.MAX_VALUE) continue; // 如果当前站点不可达，跳过
            
            for (int j = i + 1; j < n; j++) {
                if (stations[j] - stations[i] <= D) {
                    dp[j] = Math.min(dp[j], dp[i] + 1);
                } else {
                    break; // 后续站点距离过远，不可能到达
                }
            }
        }
        
        // 最终目标是到达终点，终点的下标是 n-1
        return dp[n-1] == Integer.MAX_VALUE ? -1 : dp[n-1];
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        int[] stations = new int[n];
        for (int i = 0; i < n; i++) {
            stations[i] = scanner.nextInt();
        }
        int D = scanner.nextInt();
        
        System.out.println(minRelayStations(stations, D));
    }
}