Short Java Recursion DFS + Memoization


  • 0
        int[][] mem;
        
        private int dfs(int[][] flights, int[][] days, int i, int k) {
            if(k==days[0].length)
                return 0;
            if(mem[i][k]>0)
                return mem[i][k];
            int maxVacations = 0;
            for(int n=0; n<flights[0].length; n++)
                if((n!=i && flights[i][n]==1) || n==i)
                    maxVacations = Math.max(maxVacations, days[n][k] + dfs(flights, days, n, k+1));
            mem[i][k] = maxVacations;
            return maxVacations;
        }
        
        public int maxVacationDays(int[][] flights, int[][] days) {
            mem = new int[flights.length][days[0].length];
            return dfs(flights, days, 0, 0);
        }

Log in to reply
 

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