bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
Hard2-D Dynamic ProgrammingLC 568

Maximum Vacation Days

LeetCode wants to give one of its best employees the option to travel among n cities to collect algorithm problems. But all work and no play makes Jack a dull boy, you could take vacations in some particular cities and weeks. Your job is to schedule the traveling to maximize the number of vacation days you could take, but there are certain rules and restrictions you need to follow. Rules and restrictions: 1. You can only travel among n cities, represented by indexes from 0 to n - 1. Initially, you are in the city indexed 0 on Monday. 2. The cities are connected by flights. The flights are represented as an n x n matrix (not necessarily symmetrical), called flights representing the airline status from the city i to the city j.

Asked at 4 companies
FacebookGoogleMicrosoft
Hints
  • 1.Think about which data structure fits best
  • 2.Consider the time complexity of your approach
  • 3.Look for patterns in the constraints
LeetCode