Tương tự như bài 2140. Solving Questions With Brainpower Những bài này đều có dạng: ở mỗi step i ta có thể chọn thực hiện trong 1 tập các action có thể thực hiện Đối với bài này, ở days[i], ta có thể lựa chọn:

• Mua vé 1 ngày, cộng chi phí vé 1 ngày và qua xét ngày tiếp theo
• Mua vé 7 ngày, cộng chi phí vé 7 ngày và skip qua 6 ngày kế tiếp
• Mua vé 30 ngày, cộng chi phí vé 30 ngày và skip qua 29 ngày kế tiếp Đầu tiên, dễ dàng triển khai bài toán trên bằng recursion + memo (AC beats 80%) Recursion + memo

class Solution {
    private int[] days;
    private int[] costs;
    private Map<Integer, Integer> memo;
    public int mincostTickets(int[] days, int[] costs) {
        this.days = days;
        this.costs = costs;
        memo = new HashMap<>();

        return solve(0, 0);
    }

    private int solve(int idx, int untilFreeDay) {
        if (idx >= days.length) return 0;
        if (days[idx] <= untilFreeDay) return solve(idx+1, untilFreeDay);
        if (memo.containsKey(idx)) return memo.get(idx);

        int opt = Math.min(Math.min(
            costs[0] + solve(idx+1, days[idx]),
            costs[1] + solve(idx+1, days[idx] + 6)),
            costs[2] + solve(idx+1, days[idx] + 29)
        );

        memo.put(idx, opt);
        return opt;
    }
}