Leetcode Problem 568. Maximum Vacation Days

568. Maximum Vacation Days

Leetcode Solutions

Approach # Using-D Dynamic Programming

  1. Initialize a 2-D array dp with dimensions n x (k+1) and set all values to 0.
  2. For each city i from n-1 to 0, fill dp[i][k] with days[i][k] for the last week k.
  3. For each week k from k-1 to 0, iterate over each city i: a. Set dp[i][k] to days[i][k] + dp[i][k+1] to represent staying in the same city. b. Iterate over each city j and check if a flight exists from i to j (flights[i][j] == 1). c. If a flight exists, calculate the vacation days for flying to city j: days[j][k] + dp[j][k+1]. d. Update dp[i][k] with the maximum of its current value and the value calculated for flying to city j.
  4. The answer is dp[0][0], which represents the maximum vacation days starting from city 0 in week 0.
UML Thumbnail

Approach # Using Depth First Search

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...