赞
踩
今天遇到的这道题,我知道要用动态规划,可就是想不出状态转移方程。看了题解,才明白,它倒序求得的。
题目链接如下:leetcode,最低票价
在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一年里,你要旅行的日子将以一个名为 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
题目耐心看,是可以看懂的。就是某几天你一定得坐火车, 有管一天的票,有管一周的票,还有管一月的票,怎么买,花费最少。
直接上代码,看了代码再细说。
以示例2为例来讲解代码逻辑
days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
第31天之后,都不必出行,那memo[32 ] 到memo[365]都是0,即不用花钱。
dp(31),买日票、周票、月票都可以,最小花费是买日票,即db(31) = 2
dp(30),同样是买日票得两张(30号和31号),周票、月票1张也可以,取最小花费,db(30) = 4;
dp(30) 面临三种选择
dp(31) + 2 = 2 + 2 = 4 // 买张一日票,再加上31天之后的花费
dp(37) + 7 = 0 + 7 =7 // 买张周票,再加上37天之后的
dp(60) + 15 = 0 + 15 =15// 买张周票,再加上37天之后的
dp(29),不必出单,dp(29) = dp(30) = 4;
…… ……
dp(10) 面临三种选择
dp(11) + 2 = 4 + 2 = 6 // 买张一日票,再加上11天之后的花费
dp(17) + 7 = 4 + 7 =11 // 买张周票,再加上17天之后的
dp(40) + 15 = 0 + 15 =15// 买张周票,再加上40天之后的
…… ……
从后往前,直到dp(1)就是本题答案
class Solution { int[] costs; Integer[] memo; // 计算过的,直接放数组里 Set<Integer> dayset; // 记录哪些天要从火车 public int mincostTickets(int[] days, int[] costs) { this.costs = costs; memo = new Integer[366]; dayset = new HashSet(); for(int day : days){ dayset.add(day); } return dp(1); } // 特别说明,dp(365) 返回的是 年尾这一天,坐车花的钱。 // dp(364)返回的是 第364天至365天,坐车最小花费 // dp(i) 返回的是 第i天,至第365天,坐车的最小花费 // 所以,dp(1)就是要求的结果。 private int dp(int i){ if(i > 365) return 0; if(memo[i] != null) return memo[i]; if(dayset.contains(i)){ int a = dp(i + 1) + costs[0]; int b = dp(i + 7) + costs[1]; int c = dp(i + 30) + costs[2]; memo[i] = getSmallest(a, b, c); }else{ memo[i] = dp(i + 1); } return memo[i]; } private int getSmallest(int a, int b, int c){ return Math.min(a, Math.min(b,c)); } }
优化,上述dp(11)到dp(30) 值都相等,考虑在这上面优化。
这个不好理解,拿实例去套,慢慢就懂了。
class Solution { int[] costs; int[] days; Integer[] memo; int[] ways = new int[]{1, 7, 30}; public int mincostTickets(int[] days, int[] costs) { this.costs = costs; this.days = days; memo = new Integer[days.length]; return dp(0); } private int dp(int i){ if(i >= days.length) return 0; if(memo[i] != null) return memo[i]; memo[i] = Integer.MAX_VALUE; int j = i; for(int k = 0; k < 3; k++){ while(j < days.length && days[j] < days[i] + ways[k]){ j++; } memo[i] = Math.min(memo[i], dp(j) + costs[k]); } return memo[i]; } }
动态规划难,找不出动态转移方程的动态规划更难。
多练,多想,会有质变的一天。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。