Problems/0983. (M) Minimum Cost For Tickets/Java/solution.java
class Solution {
  public int mincostTickets(int[] days, int[] costs) {
    // bottom-up dynamic programming (tabulation)

    int n = days.length;
    int[] dp = new int[n+1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
      // 1-day pass
      dp[i] = dp[i-1] + costs[0];

      int j = i-1;
      // 7-day pass
      while (j >= 0 && days[i-1] - days[j] < 7)
        j--;
      dp[i] = Math.min(dp[i], dp[j+1]+costs[1]);

      j = i-1;
      // 30-day pass
      while (j >= 0 && days[i-1] - days[j] < 30)
        j--;
      dp[i] = Math.min(dp[i], dp[j+1]+costs[2]);
    }
    return dp[n];
  }
}
