983. Minimum Cost For Tickets

二刷 07/2022

Version #1 DP

感觉这题有点难，想了很久想不出来

看了一刷的答案感觉一刷写的更好 用了一个pointer for days

一开始写了bug就是只有当i >= 7的时候才检查min，这种情况在7日票价低于1日票价的时候是有错误的

Time O(D) - D = 365

Space O(D) - D = 365

Runtime: 6 ms, faster than 17.80% of Java online submissions for Minimum Cost For Tickets.

Memory Usage: 42.4 MB, less than 33.67% of Java online submissions for Minimum Cost For Tickets.

class Solution {

    public int mincostTickets(int[] days, int[] costs) {

        Set<Integer> daySet = new HashSet<>();

        for (int d : days) {

            daySet.add(d);

        }

        // The min cost to cover travel until day i

        int[] dp = new int[366];

        for (int i = 1; i <= 365; i++) {

            if (!daySet.contains(i)) {

                dp[i] = dp[i - 1];

            } else {

                dp[i] = dp[i - 1] + costs[0];

                dp[i] = Math.min(dp[i], (i >= 7 ? dp[i - 7] : 0) + costs[1]);

                dp[i] = Math.min(dp[i], (i >= 30 ? dp[i - 30] : 0) + costs[2]);

            }

        }

        return dp[365];

    }

}

一刷

Version #1 DP

100.00 %
class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        // dp[i] - minimum cost to travel to day i
        int[] dp = new int[366];
        int daysIndex = 0;
        // Easy to know that dp[i] >= dp[j] when i > j
        for (int i = 1; i <= 365; i++) {
            if (daysIndex >= days.length || days[daysIndex] != i) {
                dp[i] = dp[i - 1];
            } else {
                daysIndex++;
                dp[i] = Math.min(dp[Math.max(0, i - 1)] + costs[0],
                                Math.min(dp[Math.max(0, i - 7)] + costs[1],
                                dp[Math.max(0, i - 30)] + costs[2]));
            }
        }
        return dp[365];
    }
}