題目

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

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的leetcode 983. Minimum Cost For Tickets | 983. 最低票价（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。