# Golang DP solution with comments

• ``````
func maxVacationDays(flights [][]int, days [][]int) int {
cities := len(days)
weeks := len(days[0])
dp := make([][]int, weeks)        // Note dp is dp[week][city], opposite of days[city][week]
_dp := func(week, city int) int { // The accessor handles the base case, which is 0 vacation days starting in city 0
if week < 0 {
if city == 0 { // Only city 0 is accessible in week -1
return 0
}
return -1 // means that the city is inaccessible
}
return dp[week][city]
}
max := func(a, b int) int {
if a > b {
return a
}
return b
}

finalBest := 0
for week := range dp {
dp[week] = make([]int, cities)
for cityTo := range dp[week] {
best := -1
for cityFrom := range dp[week] {
prev := _dp(week-1, cityFrom)                                            // best possible vacation days from previous week, if we were in cityFrom
if prev != -1 && (flights[cityFrom][cityTo] > 0 || cityFrom == cityTo) { // Can we get from CityFrom to CityTo ?
// Our total vacation till this point, assuming this trip, is the previous vacation days
// to this point + number of days we'd get in the cityTo
v := prev + days[cityTo][week]
best = max(best, v)
}
}
dp[week][cityTo] = best          // This is the best number of vacation days when ending this week in cityTo
finalBest = max(finalBest, best) // This is the absolute best for all ending cities (only useful in the last round)
}
}

return finalBest
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.