C++ 9 lines DP O(n * n * k) runtime, O(n) memory


  • 0
    V
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
        vector<int> dp(flights.size(), -1);
        dp[0] = 0;
        for (auto k = 0; k < days[0].size(); ++k) {
            auto tmp = dp;
            for (auto n = 0; n < flights.size(); ++n) {
                for (auto n1 = 0; n1 < flights.size(); ++n1) {
                    if (flights[n][n1]) tmp[n1] = max(tmp[n1], dp[n]);
                }
            }
            for (auto n = 0; n < flights.size(); ++n) dp[n] = tmp[n] != -1 ? tmp[n] + days[n][k] : -1;
        }
        return *max_element(dp.begin(), dp.end());
    }
    

Log in to reply
 

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