每日一题|983. 最低票价|动态规划、记忆化递归
本题求解最小值，思路是动态规划，但是遇到的问题是：动态规划更新的顺序和步长，以及可能存在的递归溢出问题。
1、确定dp数组含义
dp[i]表示第i天到最后一天（可能不在需要出行的天数里），需要花费的最少出行价格，也就是如果需要提前买票的价格是计算在第i天的价格的。
2、确定递推公式
对于当前的dp[i]，有3种可选的方案：1天、7天、30天，分别代表了更新后的dp位置。
dp[i] = min(dp[i + 1] + cost[0], dp[i + 7] + cost[1], dp[i + 30] + cost[2])
3、确定遍历顺序
因为当前买票的最小值依赖于之后的dp，所以是从后往前遍历，同时采用递归的写法，因为顺序遍历开销大而且判断条件比较复杂：
3.1确定终止条件：超出了365天的限制
if i > 365: return 0
3.2如果在days内的更新
return dp(i) = min(dp(i + 1) + cost[0], dp(i + 7) + cost[1], dp(i + 30) + cost[2])
3.3如果不在days内的更新
return dp(i+1)
4、确定初始化
初始化dp数组为0即可，长度为366，和days的索引保持一致。
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
duration = [1, 7, 30]
dp = [0 for _ in range(366)]
@cache
def dp(i):
if i > 365:
return 0
elif i in days:
return min(dp(i + d) + c for c, d in zip(costs, duration))
else:
return dp(i+1)
return dp(1)这里使用了Python3的@cache装饰特性，用来储存递归的新数据节省时间开销。
对于python2、java可以使用memo = {}记忆化字典来储存每一个dp，如果是新的就储存，见过的直接返回。