Lintcode 874: Maximum Vacation Days

https://www.lintcode.com/problem/maximum-vacation-days/description

Notes:

This question seems very complicated, but actually the logic to this question is very simple. Find a path with the maximum sum (or vacation days.) with some limitations.

One is that we can only move finite steps (number of the weeks), the other is that we can stay at the same node (or city).

One method is DFS + memo.

See the code below:

class Solution {
public:
    /**
     * @param flights: the airline status from the city i to the city j
     * @param days: days[i][j] represents the maximum days you could take vacation in the city i in the week j
     * @return: the maximum vacation days you could take during K weeks
     */
    int maxVacationDays(vector<vector<int>> &flights, vector<vector<int>> &days) {
        // Write your code here
        int m = flights.size(), a = days.size(), b = days[0].size();
        vector<vector<int>> g(m);
        for(int i=0; i<m; ++i) {
            g[i].push_back(i);
            for(int j=0; j<m; ++j) {
                if(flights[i][j] == 1) g[i].push_back(j);
            }
        }
        vector<vector<int>> memo(m, vector<int>(b, -1));
        return dfs(0, 0, g, days, memo);
    }

private:
    int dfs(int st, int wks, vector<vector<int>> &g, vector<vector<int>> &dys, vector<vector<int>> &memo) {
        if(wks == dys[0].size()) return 0;
        if(memo[st][wks] != -1) return memo[st][wks];
        int t = 0;
        for(auto &a : g[st]) {
            t = max(t, dys[a][wks] + dfs(a, wks+1, g, dys, memo));//find the max;
        }
        return memo[st][wks] = t;
    }
};