-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDp983.java
More file actions
35 lines (34 loc) · 1.33 KB
/
Dp983.java
File metadata and controls
35 lines (34 loc) · 1.33 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package dynamicprogramming;
public class Dp983 {
/**
*
* Runtime: 1 ms, faster than 93.15% of Java online submissions for Minimum Cost For Tickets.
* Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for Minimum Cost For Tickets.
* 计算每天的开销，
* @param days
* @param costs
* @return
*/
public int mincostTickets(int[] days, int[] costs) {
int costOne = costs[0];
int costEleven = costs[1];
int costThirsty = costs[2];
int[] dayCost = new int[366];
int dayIndex = 0;
for (int i = 1; i < 366 && dayIndex < days.length; i++) {
if (i < days[dayIndex]) {
//如果当天没有旅游，就是前一天的开销
dayCost[i] = dayCost[i-1];
} else {
/**
* 如果今天旅游了，则考虑一下今天买一天票的花销，7天前买了7天票的花销，以及30天前买了30天票的花销，
* 取最小值
*/
dayCost[i] = Math.min(dayCost[i-1] + costOne, dayCost[i-7 > -1 ? i-7 : 0] + costEleven);
dayCost[i] = Math.min(dayCost[i], dayCost[i-30 > -1 ? i-30 : 0] + costThirsty);
dayIndex ++;
}
}
return dayCost[days[days.length-1]];
}
}