Java Recursive Solution


  • 0
    S

    public class Solution {

    int[][] sol;
    public int maxVacationDays(int[][] flights, int[][] days) {
        sol = new int[days.length][days[0].length];
        
        // N*N matrix for flights data and N*K matrix for weeks data
        // [N,K] - 1,100
        // A-> B 
       return VacationDays(0, flights, days, 0, false); 
        
        
    }
    
    public int VacationDays(int current_city, int[][] flights, int[][] days, int current_week, boolean flag){
        
        if(current_week > days[0].length -1)
            return 0;
        
        
        if(sol[current_city][current_week] > 0)
            return sol[current_city][current_week];
        
        int max = Integer.MIN_VALUE;
        
        for(int j = 0; j < flights[current_city].length; j++){
            if(current_city == j){
                
               max=  Math.max(max, days[current_city][current_week] + VacationDays(j, flights, days, current_week +1, false));
                
            }
            
            else if(flights[current_city][j] == 1){
                
               if(flag == false) 
                  max=  Math.max(max, VacationDays(j, flights, days, current_week,true));
                
               max =  Math.max(max, days[current_city][current_week] + VacationDays(j, flights, days, current_week + 1, true));    
            }
            
        }
        
        sol[current_city][current_week] = max;
        
        return max;
        
        
    }
    

    }


Log in to reply
 

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