Golang DP solution with comments


  • 0
    A
    
    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
    }
    

Log in to reply
 

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