Posted on 2023-03-28 16:37
Uriel 閱讀(30)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
給出1-365天內需要旅行的日期，以及單日票，七日票，年票的價格，問最少多少錢可以cover當年的旅行開支，dp
dp[i] = min(dp[i - 1] + costs[0], dp[i - 7] + costs[1], dp[i - 30] + costs[2])
1 #983
2 #Runtime: 28 ms (Beats 74.23%)
3 #Memory: 13.2 MB (Beats 94.85%)
4
5 class Solution(object):
6 def mincostTickets(self, days, costs):
7 """
8 :type days: List[int]
9 :type costs: List[int]
10 :rtype: int
11 """
12 dp = [0] * 366
13 for i in range(1, 366):
14 if i not in days:
15 dp[i] = dp[i - 1]
16 else:
17 dp[i] = min(dp[i - 1] + costs[0], dp[max(0, i - 7)] + costs[1], dp[max(0, i - 30)] + costs[2])
18 return dp[365]