public class MinTicketFare {
static final int MONTH_PASS = 25;
static final int WEEK_PASS = 7;
static final int DAY_PASS = 2;
public static void main(String[] args) {
int[] dates = { 1, 2, 4, 5, 7, 9, 29, 30 };
int cost = findMinCost(dates);
System.out.println("Min cost =" + cost);
}
private static int findMinCost(int[] dates) {
int[] dp = new int[dates.length + 1];
dp[1] = DAY_PASS;
for (int i = 2; i < dp.length; i++) {
dp[i] = dp[i - 1] + 2;
}
for (int i = 1; i < dp.length; i++) {
// at ith day, we can either take DAY Pass or include it in our
// WEEK_PASS range.
int a = Math.min(dp[i - 1] + DAY_PASS, checkForWeekPass(dates, dp, i));
dp[i] = Math.min(dp[i], a);
// System.out.println("i=" + i + " , dp[i] = "+dp[i]+ " , dates[i] =
// "+dates[i-1] +" , checkForWeekPass(dp, i) = " + a);
}
return Math.min(MONTH_PASS, dp[dp.length - 1]);
}
private static int checkForWeekPass(int[] dates, int[] dp, int i) {
int offset = 0;
int index = getLastReachableDate(dates, i - 1);
offset = dp[index + 1];
return WEEK_PASS + offset;
}
private static int getLastReachableDate(int[] dates, int index) {
int currentDate = dates[index];
while (index > -1 && (currentDate - dates[index]) < 7) {
index--;
}
return index;
}
}
