Java DFS(TLE) and DP Solutions


  • 19

    Solution 1. DFS. The idea is just try each possible city for every week and keep tracking the max vacation days. Time complexity O(N^K). Of course it will TLE....

    public class Solution {
        int max = 0, N = 0, K = 0;
        
        public int maxVacationDays(int[][] flights, int[][] days) {
            N = flights.length;
            K = days[0].length;
            dfs(flights, days, 0, 0, 0);
            
            return max;
        }
        
        private void dfs(int[][] f, int[][] d, int curr, int week, int sum) {
            if (week == K) {
                max = Math.max(max, sum);
                return;
            }
            
            for (int dest = 0; dest < N; dest++) {
                if (curr == dest || f[curr][dest] == 1) {
                    dfs(f, d, dest, week + 1, sum + d[dest][week]);
                }
            }
        }
    }
    

    Solution 2. DP. dp[i][j] stands for the max vacation days we can get in week i staying in city j. It's obvious that dp[i][j] = max(dp[i - 1][k] + days[j][i]) (k = 0...N - 1, if we can go from city k to city j). Also because values of week i only depends on week i - 1, so we can compress two dimensional dp array to one dimension. Time complexity O(K * N * N) as we can easily figure out from the 3 level of loops.

    public class Solution {
        public int maxVacationDays(int[][] flights, int[][] days) {
            int N = flights.length;
            int K = days[0].length;
            int[] dp = new int[N];
            Arrays.fill(dp, Integer.MIN_VALUE);
            dp[0] = 0;
            
            for (int i = 0; i < K; i++) {
                int[] temp = new int[N];
                Arrays.fill(temp, Integer.MIN_VALUE);
                for (int j = 0; j < N; j++) {
                    for(int k = 0; k < N; k++) {
                        if (j == k || flights[k][j] == 1) {
                            temp[j] = Math.max(temp[j], dp[k] + days[j][i]);
                        }
                    }
                }
                dp = temp;
            }
            
            int max = 0;
            for (int v : dp) {
                max = Math.max(max, v);
            }
            
            return max;
        }
    }
    

  • 0
    T

    @shawngao Nice solution!


  • 5
    Z

    Thanks for sharing! I come out with the similar idea but haven't realized we can do some space optimization here.
    Here is my O(NK) space solution.

    public class Solution {
    
        public int maxVacationDays(int[][] flights, int[][] days) {
            int N = flights.length;
            int K = days[0].length;
            int[][] dp = new int[N][K];
            boolean[][] canReach = new boolean[N][K];
            int res = 0;
            // init : week1 start from city 0
            for (int i = 0; i < N; i++) {
                if (i == 0 || flights[0][i] == 1) {
                    // System.out.printf(" we can fly from city %d to %d in week %d\n", 0, i, 0);
                    dp[i][0] = days[i][0];
                    canReach[i][0] = true;
                }
            }
            // dp
            for (int j = 1; j < K; j++) {
                for (int i = 0; i < N; i++) {
                    for (int k = 0; k < N; k++) {
                        // we can fly from city k to i
                        if ((k == i || flights[k][i] == 1) && canReach[k][j - 1]) {
                            // System.out.printf(" we can fly from city %d to %d in week %d\n", k, i, j);
                            dp[i][j] = Math.max(dp[i][j], dp[k][j - 1] + days[i][j]);
                            canReach[i][j] = true;
                        } 
                    }
                }            
            }
            for (int i = 0; i < N; i++) {
                res = Math.max(res, dp[i][K - 1]);
            }
            return res;
        }
        
    }
    

  • 1
    Y

    @shawngao
    Similar idea by using DP. The main difference is that I use DP backward.
    The problem boils down to solving the following equation:
    V[i, k] = max( days[i][k] + V[i, k+1], days[j][k] + V[j][k+1]), where j satisfies j != i && flights[i][j] == 1, for i = 0, ... ,N-1, k = 0, ... , K-1, and V[i, k] represent the maximum vocation days in City i begining from Week k.

    Here is my code.

    public int maxVacationDays(int[][] flights, int[][] days) {
            if (days.length == 0 || flights.length == 0) return 0;
            int N = flights.length;
            int K = days[0].length;
            int[][] vocationDays = new int[N][K + 1];
            for (int k = K - 1; k >= 0; k--) {
                for (int i = 0; i < N; i++) {
                    vocationDays[i][k] = days[i][k] + vocationDays[i][k + 1];
                    for (int j = 0; j < N; j++) {
                        if (flights[i][j] == 1) {
                            vocationDays[i][k] = Math.max(days[j][k] + vocationDays[j][k + 1], vocationDays[i][k]);
                        }
                    }
                }
            }
            return vocationDays[0][0];
        }
    

  • 0
    W
    public int maxVacationDays(int[][] flights, int[][] days) {
        int N = flights.length, K = days[0].length, dp[] = new int[cities];
        Arrays.fill(dp, 1, dp.length, -1);
        for (int i = 0, j, k, temp[]; i < K; i++, dp = temp)
          for (j = 0, temp = Arrays.copyOf(dp, dp.length); j < N; j++)
            if (dp[j] >= 0) for (k = 0; k < N; k++)
              if (j == k || flights[j][k] == 1) temp[k] = Math.max(temp[k], dp[j] + days[k][i]);
        return Arrays.stream(dp).max().getAsInt();
      }

  • 1
    A

    @shawngao why do not you consider the case that the person cannot arrive the k place at the i -1 week? You just use flights[k][j] == 1 to judge if he can arrive the j place at the i week. Maybe the graph is not connected.


  • 0
    H

    @Andrewli
    I agree with you, the answer is correct only because Integer.MIN_VALUE has too much weight. If we have many more vocation days at the dis-connected city, the answer will be wrong.


  • 0
    A

    @hyj143 yes, and actually, this is bellman-ford algorithm. Many problems in leetcode are modified version of very classic algorithm problems, but I don't know why these author in discussion don't mention it.


  • 0
    P

    If you do DFS with cache, it could pass the OJ, my result is 600ms.

    public int maxVacationDays(int[][] flights, int[][] days) {
        int N = flights.length, K = days[0].length;
        int[][] cache = new int[K][N];
        for(int i=0; i<K; i++){
            Arrays.fill(cache[i], -1);
        }
        return DFS(flights, days, 0, 0, cache);
    }
    
    private int DFS(int[][] flights, int[][] days, int k, int i, int[][] cache){
        int N = flights.length, K = days[0].length;
        if(k==K) return 0;
        if(cache[k][i]>=0) return cache[k][i];
        int max = 0;
        for(int j=0; j<N; j++){
            if(i==j || flights[i][j]==1){
                int temp = DFS(flights, days, k+1, j, cache)+days[j][k];
                max = Math.max(max, temp);
            }
        }
        cache[k][i] = max;
        return max;
    }

  • 0
    A

    What is TLE with DFS ?


  • 0
    A

    @amit65 got it.Time limit Exceeded


Log in to reply
 

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