Python教程

Leetcode 983. Minimum Cost For Tickets [Python]

本文主要是介绍Leetcode 983. Minimum Cost For Tickets [Python]，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目给了状态转移公示：
dp[i]表示第i天以及往后旅行需要的最小花费。我们需要每次花钱都覆盖尽可能多的天数。
dp[i] = dp[i+1] + 1daypass fee 或者是= dp[i+7] + 7daypass fee 或者是 = dp[i+30] + 30daypass fee三者中最小的。则dp[days[0]] 表示从第一个日期到后面的全部需要旅行的时间都被覆盖需要的最小花费。

from functools import lru_cache
class Solution:
	def fun(self, days, costs):
		days = set(days)
		durations = [1,7,30]
		@lru_cache(None)
		def dp(i):
			if i > 365:return 0
			elif i in days:
				return min(dp(i+d)+c for d,c in zip(durations, costs))
			else:
				return dp(i+1)
		return dp(1)
这篇关于Leetcode 983. Minimum Cost For Tickets [Python]的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航