高质量的高密网站建设,找工地项目承包网站,旅游建设门户网站的方案,安装wordpress邮件提示503983. 最低票价
题干
在一个火车旅行很受欢迎的国度#xff0c;你提前一年计划了一些火车旅行。在接下来的一年里#xff0c;你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。
火车票有 三种不同的销售方式 #xff1a;
一张 为期一天 的通…983. 最低票价
题干
在一个火车旅行很受欢迎的国度你提前一年计划了一些火车旅行。在接下来的一年里你要旅行的日子将以一个名为 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并完成了你计划的每一天旅行。
题解
暴力递归改动态规划 这里非常不好做的是边界的判断 出现问题后也不好定位
public static int mincostTickets(int[] days, int[] costs) { return f(0, days, costs);
} public static int f(int index, int[] days, int[] costs) { if (index days.length) { return 0; } // 使用一天的花费 int res f(index 1, days, costs) costs[0]; for (int i index; i days.length; i) { if (days[i] - days[index] 7) { int f2 f(i 1, days, costs) costs[1]; res Math.min(res, f2); } else { break; } }for (int i index; i days.length; i) { if (days[i] - days[index] 15) { int f2 f(i 1, days, costs) costs[2]; res Math.min(res, f2); } else { break; } }return res;
}这个暴力递归的写法有个很严重的问题不应该循环进行递归。 public static int mincostTickets(int[] days, int[] costs) { int length days.length; int[] dp new int[length 1]; dp[length] 0; for (int index length - 1; index 0; index--) { int res dp[index 1] costs[0]; int index2 index; while (index2 length days[index2] - days[index] 7) { // 和当前相等肯定可以进来因此index2已经进行1操作可以直接传递下去 index2; } int f2 dp[index2] costs[1]; res Math.min(res, f2); int index3 index; while (index3 length days[index3] - days[index] 30) { index3; } int f3 dp[index3] costs[2]; res Math.min(res, f3); dp[index] res; } return dp[0];
}这里换成dp的时候已经纠正过来了 这里的写法还有一个问题index2和index3 每次都是从index开始遍历的 但是用时更快的写法是index2index3从0开始不回退。index也是从0开始 比如 index为0时候 index3为9满足了30天的条件当index为1的时候难道index为3以及之前还不能满足吗。显然不会。
总结
这个题目的days[index] 7 用小于号还是小于等于递归下去是否还要加1的边界判断比较容易绕晕 另外7天的签证可以比1天的签证便宜所有必须3种情况都递归下去
