Maximum Vacation Days

题目
LeetCode wants to give one of its best employees the option to travel among N cities to collect algorithm problems. But all work and no play makes Jack a dull boy, you could take vacations in some particular cities and weeks. Your job is to schedule the traveling to maximize the number of vacation days you could take, but there are certain rules and restrictions you need to follow.

答案

dfs

    public int maxVacationDays(int[][] flights, int[][] days) {
        return recur(flights, days, 0, 0);
    }

    public int recur(int[][] flights, int[][] days, int curr_city, int curr_week) {
        if(curr_week == days.length) {
            return 0;
        }
        int max = 0;
        // How about fly to the other N - 1 cities
        for(int i = 0; i < flights[0].length; i++) {
            if(flights[curr_city][i] == 1 || curr_city == i){
                int ret = recur(flights, days, i, curr_week + 1) + days[i][curr_week];
                max = Math.max(max, ret);
            }
        }
        return max;
    }

dfs + memorization

class Solution {
    public int maxVacationDays(int[][] flights, int[][] days) {
        int[][] dp = new int[flights.length][days[0].length];
        for(int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], -1);
        }
        return recur(dp, flights, days, 0, 0);
    }

    public int recur(int[][] dp, int[][] flights, int[][] days, int curr_city, int curr_week) {
        if(curr_week == days[0].length) {
            return 0;
        }
        int max = 0;
        if(dp[curr_city][curr_week] != -1) return dp[curr_city][curr_week];

        // How about fly to the other N - 1 cities
        for(int i = 0; i < flights[0].length; i++) {
            if(flights[curr_city][i] == 1 || curr_city == i){
                int ret = recur(dp, flights, days, i, curr_week + 1) + days[i][curr_week];
                max = Math.max(max, ret);
            }
        }
        dp[curr_city][curr_week] = max;
        return max;
    }
}

dp

class Solution {
    public int maxVacationDays(int[][] flights, int[][] days) {
        int N = flights.length, K = days[0].length;
        int[][] dp = new int[N][K + 1];
        // Base cases
        for(int i = 0; i < N; i++) {
            dp[i][K] = 0;
        }

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

                }
                max = Math.max(max, dp[j][i]);
            }
        }
        return dp[0][0];
    }
}