金币路径

/*
 * LeetCode 656: Coin Path (Using Java Streams)
 * Given an array A (index starts at 1) consisting of N integers: A1, A2, ..., AN and an integer B. 
 * The integer B denotes that from Ai, you can jump to Ai+1, Ai+2, ..., Ai+B if 1 <= i + j <= N. 
 * Find the minimum cost path to reach AN from A1, and output the indices of this path. 
 * If there are multiple paths with the same cost, return the lexicographically smallest such path. 
 * If no such path exists, return an empty list.
 */
 
import java.util.*;
import java.util.stream.*;
 
public class CoinPathStream {
    public List<Integer> cheapestJump(int[] A, int B) {
        int N = A.length;
        int[] cost = new int[N];
        int[] path = new int[N];
        Arrays.fill(cost, Integer.MAX_VALUE);
        cost[0] = 0;
        List<Integer>[] res = new List[N];
        for (int i = 0; i < N; i++) res[i] = new ArrayList<>();
        res[0].add(1);
 
        IntStream.range(0, N).forEach(i -> {
            if (A[i] == -1) return;
            IntStream.range(i + 1, Math.min(i + B + 1, N)).forEach(j -> {
                if (A[j] == -1) return;
                int newCost = cost[i] + A[j];
                if (newCost < cost[j]) {
                    cost[j] = newCost;
                    path[j] = i;
                    res[j] = new ArrayList<>(res[i]);
                    res[j].add(j + 1);
                } else if (newCost == cost[j]) {
                    List<Integer> newPath = new ArrayList<>(res[i]);
                    newPath.add(j + 1);
                    if (comparePaths(newPath, res[j]) < 0) {
                        res[j] = newPath;
                    }
                }
            });
        });
 
        return res[N - 1];
    }
 
    private int comparePaths(List<Integer> path1, List<Integer> path2) {
        for (int i = 0; i < Math.min(path1.size(), path2.size()); i++) {
            if (!path1.get(i).equals(path2.get(i))) {
                return path1.get(i) - path2.get(i);
            }
        }
        return path1.size() - path2.size();
    }
}