Posted on 2023-03-28 16:37
Uriel 阅读(12)
评论(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]