983.minimum-cost-for-tickets.md

983. Minimum Cost For Tickets

Dynamic Programming

The minimum cost up to day i (including) depends on the minimum cost from day i-1, i-7, and i-30. On each travel day, we have three choices: buy a 1-day ticket, buy a 7-day ticket, or buy a 30-day ticket. We can break down the problem into subproblems, so we can use dynamic programming to solve this problem.

We can use dp[i] to represent the minimum cost of tickets need to cover all travel days up to and including day i. The goal is fill up this dp array by finding the minimum cost for each day, and the final answer wil be dp[lastDay].

To find the minimum cost for tickets up to day i (dp[i]), we can use the following formula:

• If a 1-day ticket on day i: dp[i] = dp[i - 1] + cost[0]
• If a 7-day ticket ending on day i: dp[i] = min(dp[i - 7], dp[i - 6] ... dp[i - 1]) + cost[1]
• If a 30-day ticket ending on day i: dp[i] = min(dp[i - 30], dp[i - 29] ... dp[i - 1]) + cost[2]

But since the value of dp array is non-decreasing, we can simplify the above formula to:

• For a 7-day ticket ending on day i: dp[i - 7] + cost[1], because dp[i - 7] <= dp[i - 6] ... dp[i - 1].
• For a 30-day ticket ending on day i: dp[i - 30] + cost[2], because dp[i - 30] <= dp[i - 29] ... dp[i - 1].

Nice explanation: https://leetcode.com/problems/minimum-cost-for-tickets/solutions/227130/java-dp-solution-with-detailed-comment-and-explanation/

fun mincostTickets(days: IntArray, costs: IntArray): Int {
    val lastDay = days[days.size - 1]
    val dp = IntArray(lastDay + 1)

    val goTravels = BooleanArray(lastDay + 1)
    for (day in days) {
        goTravels[day] = true
    }

    // We have to iterate everyday, not just `days` items, so
    //  that we can build the table.
    for (i in 1..lastDay) {
        if (goTravels[i]) {
            // One day minimum cost, we don't find the minimum with dp[i]
            dp[i] = dp[i - 1] + costs[0]
            dp[i] = minOf(dp[i], dp[if (i > 7) i - 7 else 0] + costs[1])
            dp[i] = minOf(dp[i], dp[if (i > 30) i - 30 else 0] + costs[2])
        } else {
            // Don't travel, then the cost is previous day.
            dp[i] = dp[i - 1]
        }
    }                
    return dp[lastDay]
}