public class HotelStops {
    /**
     * input = { 190, 420, 550, 660, 670 };
     * penalties = {0, 100, 1000, 5900, 2600, 3500};
     * prev = {-1, 0, 1, 2, 2, 2);
     * result = {1, 2, 5} stop at 190, 420, 670
     * To recover the path from minimum penalties, while
     * computing penalties[i], we also note down prev[i],
     * the next to last stop on the minimum stop to i
     */
    public static List<Integer> hotelStops(int[] input) {
        List<Integer> result = new ArrayList<Integer>();
        int[] penalties = new int[input.length + 1];
        int[] prev = new int[input.length + 1];
        penalties[0] = 0;
        prev[0] = -1;
        for (int i = 1; i < penalties.length; i++) {
            penalties[i] = (int) Math.pow(200 - input[i - 1], 2);
            prev[i] = 0;
            for (int j = 1; j < i; j++) {
                int cur = penalties[j] + (int) Math.pow(200 - (input[i - 1] - input[j - 1]), 2);
                if (cur < penalties[i]) {
                    penalties[i] = cur;
                    prev[i] = j;
                }
            }
        }
        System.out.println(Arrays.toString(penalties));
        System.out.println(Arrays.toString(prev));
        int idx = prev.length - 1;
        while (prev[idx] != -1) {
            result.add(idx);
            idx = prev[idx];
        }
        Collections.reverse(result);
        System.out.println(result);
        return result;
    }
    public static void main(String[] args) {
        int[] input = { 190, 420, 550, 660, 670 };
        HotelStops.hotelStops(input);
    }
}