leetcode 983. Minimum Cost For Tickets | 983. 最低票价（动态规划）

题目https://leetcode.com/problems/minimum-cost-for-tickets/题解没想出来，看了官方题解，难点在于如何列出 dp 的状态转移方程。我没想到它的子问题是可以以这种“贪心”的方式求解的。class Solution {public int mincostTickets(int[] days, int[] costs) {HashSet<Inte

寒泉Hq

48166人浏览 · 2021-07-17 20:53:18

寒泉Hq · 2021-07-17 20:53:18 发布

题目

https://leetcode.com/problems/minimum-cost-for-tickets/
在这里插入图片描述

题解

没想出来，看了官方题解，难点在于如何列出 dp 的状态转移方程。我没想到它的子问题是可以以这种“贪心”的方式求解的。
在这里插入图片描述

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        HashSet<Integer> daySet = new HashSet<>();
        for (int day : days) {
            daySet.add(day);
        }
        int lastDay = days[days.length - 1];
        int[] dp = new int[365 + 30 + 1]; // 扩充30天且默认值为0，可以省掉+1,+7,+30的越界判断
        dp[lastDay] = Math.min(costs[0], Math.min(costs[1], costs[2]));
        for (int i = lastDay - 1; i >= 0; i--) {
            if (daySet.contains(i)) {
                dp[i] = min(dp[i + 1] + costs[0], dp[i + 7] + costs[1], dp[i + 30] + costs[2]);
            } else {
                dp[i] = dp[i + 1];
            }
        }

        return dp[1];
    }
    public int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}