网站建设功能选择表,东莞市建设网站,如何 网站优化,wordpress视频没图像本题求解最小值#xff0c;思路是动态规划#xff0c;但是遇到的问题是#xff1a;动态规划更新的顺序和步长#xff0c;以及可能存在的递归溢出问题。
1、确定dp数组含义
dp[i]表示第i天到最后一天#xff08;可能不在需要出行的天数里#xff09;#xff0c;需要花费…
本题求解最小值思路是动态规划但是遇到的问题是动态规划更新的顺序和步长以及可能存在的递归溢出问题。
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(i1)
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)]cachedef dp(i):if i 365:return 0elif i in days:return min(dp(i d) c for c, d in zip(costs, duration))else:return dp(i1)return dp(1)
这里使用了Python3的cache装饰特性用来储存递归的新数据节省时间开销。
对于python2、java可以使用memo {}记忆化字典来储存每一个dp如果是新的就储存见过的直接返回。
