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.
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
Thus, we need to find the maximum vacation days calculated from city 0 during the week 0.
For example, if we had only a single week, the result would have been the maximum days for each city that can be flown from city 0. For more weeks, we just add it up in a similar way.
As we are recursing, we trace same decision paths multiple times. We can use memoization to prune unneeded recalculations.
Instead of doing a top-down procedure from the beginning, we can do a bottom-up solution from the beginning too, with dynamic programming.
We store the amount of maximum cumulative vacation days we can get at any city in some array. Initially, we fill the array with -1's for cities that can't be visited. If it's flyable from the zeroth city, we give it the count days[0][city]. After that, for each week, we update the maximum vacation days by considering all possibilities of either staying some city, or flying from this city to another city, which counts for calculating that another city.
At the end, we basically return the maximum for all citiies.
This dynamic programming problem is quite similar to #298 and #44, in their cumulative structure.
Resolves: #233
Here, I recommend first identifying what the problem means. To sum up, we start at the city
0. For each week including the0., we can either choose to be in another city count its vacation days or stay in our current city and count its vacation days.We can easily derive a recursive formula for this: Maximum vacation days for week
wat citycis maximum of: vacation days in the next citytduring weekw+ maximum vacation days for weekw+1at cityt, for all citiesflights[c][t] == 1 or c==tThus, we need to find the maximum vacation days calculated from city
0during the week0. For example, if we had only a single week, the result would have been the maximum days for each city that can be flown from city0. For more weeks, we just add it up in a similar way.As we are recursing, we trace same decision paths multiple times. We can use memoization to prune unneeded recalculations.
Instead of doing a top-down procedure from the beginning, we can do a bottom-up solution from the beginning too, with dynamic programming. We store the amount of maximum cumulative vacation days we can get at any city in some array. Initially, we fill the array with -1's for cities that can't be visited. If it's flyable from the zeroth city, we give it the count
days[0][city]. After that, for each week, we update the maximum vacation days by considering all possibilities of either staying some city, or flying from this city to another city, which counts for calculating that another city.At the end, we basically return the maximum for all citiies.
This dynamic programming problem is quite similar to #298 and #44, in their cumulative structure.