import java.util.HashMap;
import java.util.Map;

public class Calculator {
    public static Map<Integer, Integer> buyPass(int[] schedule) {
        Map<Integer, Integer> result = new HashMap<>();
        dfs(result, schedule, 0, 0);
        return result;
    }

    private static int dfs(Map<Integer, Integer> map, int[] plan, int start, int money) {
        if (map.containsKey(start)) {
            return map.get(start);
        }
        while (start < plan.length && plan[start] == 0) {
            start++;
        }
        if (start >= plan.length) {
            return money;
        }

        Map<Integer, Integer> map1 = new HashMap<>(map);
        Map<Integer, Integer> map2 = new HashMap<>(map);
        int m1 = dfs(map1, plan, start + 1, money + 2);
        int m2 = dfs(map2, plan, start + 2, money + 3);

        map.clear();
        Map<Integer, Integer> tmp = m1 > m2 ? map2 : map1;
        for (int key : tmp.keySet()) {
            map.put(key, tmp.get(key));
        }
        map.put(start, m1 > m2 ? 2 : 1);
        return m1 > m2 ? m2 : m1;
    }

    public static void main(String[] args) {
        int[] schedule = {1, 0, 1, 1, 0, 0, 1};
        Map<Integer, Integer> map = Calculator.buyPass(schedule);
        System.out.println(map);
    }
}