有3种票:1天,7天,30天的,它们的票价在costs数组里。
days数组里面是你要出游的日期,一年里面的第几天。范围是1~365.
求能覆盖所有出游日期的最少票钱。
思路:
DP
必然要记录不同方案的票钱,选最小值,所以用到DP。
假如在day1买了3种不同的票,那么买票钱是
cost[0] + dp[day+1]
cost[1] + dp[day+7]
cost[2] + dp[day+30]
可以看到,这个dp[i] 是由它后面的dp决定的,
而且并不是每天都出游,遇到休息天就看它后一天的,一直遇到出游天再计算。
如何记录休息天呢?可以直接和days里面的数字比较,也可以用一个boolean数组记录。
超出最后一天时,旅游结束,不需要再买票了,所以返回0.
public int mincostTickets(int[] days, int[] costs) {
int n = days.length;
boolean[] valid = new boolean[days[n-1]+1];
Integer[] dp = new Integer[valid.length];
for(int day : days) valid[day] = true;
return dfs(days[0], costs, valid, dp);
}
int dfs(int day, int[] costs, boolean[] valid, Integer[] dp) {
if(day >= valid.length) return 0;
if(dp[day] != null) return dp[day];
if(valid[day]) {
int c1 = costs[0] + dfs(day+1, costs, valid, dp);
int c2 = costs[1] + dfs(day+7, costs, valid, dp);
int c3 = costs[2] + dfs(day+30, costs, valid, dp);
return dp[day] = Math.min(c1, Math.min(c2, c3));
} else {
return dp[day] = dfs(day+1, costs, valid, dp);
}
}