Leetcode 983. Minimum Cost For Tickets [Python]
2021/12/31 11:07:40
本文主要是介绍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]的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python