LC: 568. Maximum Vacation Days - spiralgo/algorithms GitHub Wiki

568. Maximum Vacation Days:

The Essence: A quote by Erdem will make what the questions wants clear:

Here, I recommend first identifying what the problem means. To sum up, we start at the city 0. For each week including the 0., we can either choose to be in another city count its vacation days or stay in our current city and count its vacation days.

Details:

We can easily derive a recursive formula for this: Maximum vacation days for week w at city c is maximum of: vacation days in the next city t during week w + maximum vacation days for week w+1 at city t, for all cities flights[c][t] == 1 or c==t

For a detailed explanation, please refer to: https://github.com/spiralgo/algorithms/pull/377