📓
Algorithms
  • Introduction to Data Structures & Algorithms with Leetcode
  • Strings
    • Dutch Flags Problem
      • List Partitoning
    • Counters
      • Majority Vote
      • Removing Parentheses
      • Remove Duplicates from Sorted Array
    • Maths
      • Lone Integer
      • Pigeonhole
      • Check If N and Its Double Exist
      • Find Numbers with Even Number of Digits
    • Two Pointers
      • Remove Element
      • Replace Elements with Greatest Element on Right Side
      • Valid Mountain Array
      • Sort Array by Parity
      • Squares of a Sorted Array
      • Max Consecutive Ones
    • Sliding Window
      • Max Consecutive Ones 3
    • Stacks
      • Balanced Brackets
    • General Strings & Arrays
      • Move Zeros
      • Unique Elements
      • Merge Sorted Array
    • Matrices
      • Valid Square
      • Matrix Search Sequel
  • Trees
    • Untitled
  • Recursion
    • Introduction
    • Backtracking
      • Permutations
  • Dynamic Programming
    • Introduction
    • Minimum (Maximum) Path to Reach a Target
      • Min Cost Climbing Stairs
      • Coin Change
      • Minimum Path Sum
      • Triangle
      • Minimum Cost to Move Chips to The Same Position
      • Consecutive Characters
      • Perfect Squares
    • Distinct Ways
      • Climbing Stairs
      • Unique Paths
      • Number of Dice Rolls with Target Sum
    • Merging Intervals
      • Minimum Cost Tree From Leaf Values
    • DP on Strings
      • Levenshtein Distance
      • Longest Common Subsequence
  • Binary Search
    • Introduction
      • First Bad Version
      • Sqrt(x)
      • Search Insert Position
    • Advanced
      • KoKo Eating Banana
      • Capacity to Ship Packages within D Days
      • Minimum Number of Days to Make m Bouquets
      • Split array largest sum
      • Minimum Number of Days to Make m Bouquets
      • Koko Eating Bananas
      • Find K-th Smallest Pair Distance
      • Ugly Number 3
      • Find the Smallest Divisor Given a Threshold
      • Kth smallest number in multiplication table
  • Graphs
    • Binary Trees
      • Merging Binary Trees
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Inorder Traversal
      • Symmetric Tree
      • Populating Next Right Pointers in Each Node
      • Populating Next Right Pointers in Each Node II
      • 106. Construct Binary Tree from Inorder and Postorder Traversal
      • Serialise and Deserialise a Linked List
      • Maximum Depth of Binary Tree
      • Lowest Common Ancestor of a Binary Tree
    • n-ary Trees
      • Untitled
      • Minimum Height Trees
    • Binary Search Trees
      • Counting Maximal Value Roots in Binary Tree
      • Count BST nodes in a range
      • Invert a Binary Tree
      • Maximum Difference Between Node and Ancestor
      • Binary Tree Tilt
  • Practice
  • Linked Lists
    • What is a Linked List?
    • Add Two Numbers
      • Add Two Numbers 2
    • Reverse a Linked List
    • Tortoise & Hare Algorithm
      • Middle of the Linked List
  • Bitshifting
    • Introduction
  • Not Done Yet
    • Uncompleted
    • Minimum Cost For Tickets
    • Minimum Falling Path Sum
Powered by GitBook
On this page

Was this helpful?

  1. Not Done Yet

Minimum Cost For Tickets

PreviousUncompletedNextMinimum Falling Path Sum

Last updated 4 years ago

Was this helpful?

In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array days. Each day is an integer from 1 to 365.

Train tickets are sold in 3 different ways:

  • a 1-day pass is sold for costs[0] dollars;

  • a 7-day pass is sold for costs[1] dollars;

  • a 30-day pass is sold for costs[2] dollars.

The passes allow that many days of consecutive travel. For example, if we get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: 
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total you spent $11 and covered all the days of your travel.

Let's see an example of this. Given the array:

days = [1, 4, 6, 7, 8, 20]

And the ticket costs:

costs = [2, 7, 15]

We want to find out the minimum cost to travel everyday in the given list. Essentially, saving us money.

Costs is:

cost[0] = 1 day
cost[1] = 7 days
costs[2] = 30 days

Let's try to build this into a recurrence.

Base case

1 day = cost[0]

Divide & Conquer

Everyday after this is either the minimum cost of the previous days, or the current ticket.

So if we are at 7 days, our cost will either be:

  • Day 6's ticket (assuming it covers that day)

  • Day 7's cost[1] ticket

While calculating the min, we need to make sure our ticket does not exceed the days. We can visualise this with a table:

This methodology quickly falls apart, as our recurrence will look like:

  • Previous days ticket (assuming the day is covered)

Greedy search for the ticket

https://leetcode.com/problems/minimum-cost-for-tickets/
https://leetcode.com/problems/minimum-cost-for-tickets/discuss/630868/explanation-from-someone-who-took-2-hours-to-solve