Buy tickets

solution.java

class Solution {
    public int solution(int[] A) {
        int[] dp = new int[31]; // dp[i] stores the minimum cost to travel up to day i
        int n = A.length;
        int travelIndex = 0; // pointer to the current travel date
        
        for (int i = 1; i <= 30; i++) {
            if (travelIndex < n && i == A[travelIndex]) { // if i is a travel date
                int oneDayCost = dp[i - 1] + 2; // cost if using a 1-day ticket on day i
                int sevenDayCost = i > 7 ? dp[i - 7] + 7 : 7; // cost if using a 7-day ticket on day i
                int thirtyDayCost = dp[i - 30] + 25; // cost if using a 30-day ticket on day i
                dp[i] = Math.min(oneDayCost, Math.min(sevenDayCost, thirtyDayCost));
                travelIndex++; // move to the next travel date
            } else {
                dp[i] = dp[i - 1]; // no travel on day i, cost same as previous day
            }
        }
        
        return dp[30]; // return the minimum cost for the whole month
    }
}