Re: [閒聊] 每日LeetCode已回收
983. Minimum Cost For Tickets
一年有365天，其中幾天我們要搭火車出去玩，火車賣的票有1天、7天、30天三種，
求出要怎麼買票花最少錢。
Example :
Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel
your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4,
..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.
思路：
1.當天的花費和前幾天的花費有關很明顯是動態規劃的題型，首先把所有要旅遊的天數
標起來。
2.第0天的成本為0，從第1天遍歷到旅遊的最後一天，如果當前天數沒旅遊那當天的成本
一定是昨天的成本，否則就從前7天、前30天的成本和今天買票的成本三者之中取小。
3.返回最後一天的成本即可。
Java Code：
-------------------------------------------------
class Solution {
public int mincostTickets(int[] days, int[] costs) {
int n = days.length;
int[] dp = new int[days[n - 1] + 1];
dp[0] = 0;
for (int day: days) {
dp[day] = Integer.MAX_VALUE;
}
for (int i = 1; i < dp.length; i++) {
if (dp[i] == 0) {
dp[i] = dp[i - 1];
continue;
}
int n1 = dp[i - 1] + costs[0];
int n2 = i > 7 ? dp[i - 7] + costs[1] : costs[1];
int n3 = i > 30 ? dp[i - 30] + costs[2] : costs[2];
dp[i] = Math.min(n1, Math.min(n2, n3));
}
return dp[days[n - 1]];
}
}
-------------------------------------------------
--
https://i.imgur.com/fHpKflu.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1679998049.A.C06.html
討論串 (同標題文章)
完整討論串 (本文為第 274 之 719 篇)：