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

秒速五厘米 2022-08-30 00:48 174阅读 0赞

## 题目 ##

[https://leetcode.com/problems/minimum-cost-for-tickets/][https_leetcode.com_problems_minimum-cost-for-tickets]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

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

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));
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_minimum-cost-for-tickets]: https://leetcode.com/problems/minimum-cost-for-tickets/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/8a15da6c6b07488a876fb4d879ca927e.png
[Link 1]: https://leetcode.com/problems/minimum-cost-for-tickets/solution/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/e83a6fdbeb4a4ba98d3e95b261495b25.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/0ecdbbdb94cf47448a43d452aba056bd.png