Leetcode Problem 983. Minimum Cost For Tickets

983. Minimum Cost For Tickets

Leetcode Solutions

Bottom-up Dynamic Programming

  1. Initialize a dp array with a size of the last day we need to travel plus 1, all values set to 0.
  2. Initialize i = 0, representing the index for the next travel day in days.
  3. Iterate over the days from 1 to the last day in days.
    • If the current day is less than days[i], set dp[day] to dp[day - 1].
    • Otherwise, calculate dp[day] as the minimum of dp[day - 1] + costs[0], dp[max(day - 7, 0)] + costs[1], and dp[max(day - 30, 0)] + costs[2]. Increment i.
  4. Return dp[lastDay], where lastDay is the last value in days.
UML Thumbnail

Top-Down Dynamic Programming with Memoization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...