网页制作与网站开发 实验报告,wordpress销售,wordpress菜单美化,自学做包装设计的步骤1. 题目
在一个火车旅行很受欢迎的国度#xff0c;你提前一年计划了一些火车旅行。 在接下来的一年里#xff0c;你要旅行的日子将以一个名为 days 的数组给出。 每一项是一个从 1 到 365 的整数。
火车票有三种不同的销售方式#xff1a;
一张为期一天的通行证售价为 co…1. 题目
在一个火车旅行很受欢迎的国度你提前一年计划了一些火车旅行。 在接下来的一年里你要旅行的日子将以一个名为 days 的数组给出。 每一项是一个从 1 到 365 的整数。
火车票有三种不同的销售方式
一张为期一天的通行证售价为 costs[0] 美元
一张为期七天的通行证售价为 costs[1] 美元
一张为期三十天的通行证售价为 costs[2] 美元。通行证允许数天无限制的旅行。 例如如果我们在第 2 天获得一张为期 7 天的通行证 那么我们可以连着旅行 7 天第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。
示例 1
输入days [1,4,6,7,8,20], costs [2,7,15]
输出11
解释
例如这里有一种购买通行证的方法可以让你完成你的旅行计划
在第 1 天你花了 costs[0] $2 买了一张为期 1 天的通行证它将在第 1 天生效。
在第 3 天你花了 costs[1] $7 买了一张为期 7 天的通行证它将在第 3, 4, ..., 9 天生效。
在第 20 天你花了 costs[0] $2 买了一张为期 1 天的通行证它将在第 20 天生效。
你总共花了 $11并完成了你计划的每一天旅行。示例 2
输入days [1,2,3,4,5,6,7,8,9,10,30,31], costs [2,7,15]
输出17
解释
例如这里有一种购买通行证的方法可以让你完成你的旅行计划
在第 1 天你花了 costs[2] $15 买了一张为期 30 天的通行证它将在第 1, 2, ..., 30 天生效。
在第 31 天你花了 costs[0] $2 买了一张为期 1 天的通行证它将在第 31 天生效。
你总共花了 $17并完成了你计划的每一天旅行。提示
1 days.length 365
1 days[i] 365
days 按顺序严格递增
costs.length 3
1 costs[i] 1000来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-cost-for-tickets 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
dp[i] 表示第 i 天花的最少的钱上一次花的钱是 dp[days[i-1]]3种票的选择costs[k]后面相应的天数的总的花费为dp[days[i-1]]costs[k]同一天的不同花费取 min
class Solution {
public:int mincostTickets(vectorint days, vectorint costs) {vectorint dp(366,INT_MAX);//dp[i]表示第i天花的最少的钱int d[3] {1,7,30};//票的有效期int i, j, k, n days.size();for(i 0; i 3; i)//初始化第一天的选择3种选择for(j days[0]; j min(366,days[0]d[i]); j){ //后面的天都不用再花钱重叠的时间取最小的花费dp[j] min(dp[j], costs[i]);}for(i 1; i n; i){ //遍历从第2天开始的其余的天for(k 0; k 3; k)//三种票选择for(j days[i]; j min(366,days[i]d[k]); j){ //上一次花的钱是 dp[days[i-1]],这次花的钱costs[k]dp[j] min(dp[j], dp[days[i-1]]costs[k]);}}return dp[days[n-1]];//最后一次的最小花费}
};以后出去玩耍可以先动态规划一下哈哈
