983.js

/** ------------------------------------------------------------------------------
 * 
 * 983. Minimum Cost For Tickets
 * Topics: DP
 * https://leetcode.com/problems/minimum-cost-for-tickets/description/?envType=daily-question&envId=2024-12-31
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {number[]} days
 * @param {number[]} costs
 * @return {number}
 */
var mincostTickets = function (days, costs) {
  const n = days[days.length - 1]
  const dp = new Array(n + 1).fill(0)

  let i = 0
  for (let day = 1; day <= n; day++) {
    if (day === days[i]) {
      dp[day] = Math.min(
        dp[day - 1] + costs[0],
        dp[Math.max(0, day - 7)] + costs[1],
        dp[Math.max(0, day - 30)] + costs[2],
      )
      i++
    } else {
      dp[day] = dp[day - 1]
    }
  }
  return dp[n]
}

// console.log(mincostTickets([1, 4, 6, 7, 8, 20], [2, 7, 15]))
console.log(mincostTickets([1, 4, 6, 7, 8, 365], [2, 7, 15]))

/**
 * 조금 비효율적이긴 하나, 명확하게 보이는 dp + visited 배열 풀이
 * 복잡도 O(365)
 */
var mincostTickets = function (days, costs) {
  const dp = new Array(366).fill(0)
  const visited = new Array(366).fill(0)

  for (let i = 0; i < days.length; i++) {
    visited[days[i]] = 1
  }

  for (let i = 1; i < 366; i++) {
    if (!visited[i]) {
      dp[i] = dp[i - 1]
      continue
    }

    // dp[i] = Math.min(dp[i - 1] + costs[0], dp[Math.max(0, i - 7)] + costs[1], dp[Math.max(0, i - 30)] + costs[2])

    dp[i] = dp[i - 1] + costs[0]

    if (dp[i - 1] + costs[0] > costs[1]) {
      const day = Math.max(0, i - 7)
      dp[i] = Math.min(dp[day] + costs[1], dp[i])
    }

    if (dp[i - 1] + costs[0] > costs[2]) {
      const day = Math.max(0, i - 30)
      dp[i] = Math.min(dp[day] + costs[2], dp[i])
    }
  }

  return dp[days[days.length - 1]]
}