[568. Maximum Vacation Days] C++_1dimensional vector_DP


  • 0

    dp[i][j] stands for the maximized wks if we want spend the j-th week at destination i.
    so: dp[i][j] = days[i][j] + max(dp[k][j-1]) for k = 0, 1, `````, N-1.

    1-dimensional vector:
    Time: O(N^2 * K) and Space: O(N)

    class Solution {
    public:
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
        int N = flights.size();//number of cities
        int K = days[0].size();//number of wks
        vector<int> dp(N, INT_MIN);
        vector<int> vec(N, INT_MIN);
        int cur_max = days[0][0];
        dp[0] = days[0][0];
        for(int i = 1; i < N; ++i){
            if(flights[0][i]){
                dp[i] = days[i][0];
                cur_max = max(cur_max, dp[i]);
            }
        }
        for(int j = 1; j < K; ++j){//current wks
            for(int i = 0; i < N; ++i){//current position
                int tmp_max = INT_MIN;
                for(int k = 0; k < N; ++k){//previous destination
                    if(dp[k] == INT_MIN || (k != i && flights[k][i] == 0)) continue;
                    tmp_max = max(tmp_max, dp[k] + days[i][j]);
                }
                vec[i] = tmp_max;
                cur_max = max(cur_max, vec[i]);
            }
            dp = vec;
        }
        return cur_max;
     }
    };
    

    Two-dimensional vector:
    AC: Time: O(KN^2), Space: O(N * K)*

    class Solution {
    public:
    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
        int N = flights.size();//number of cities
        int K = days[0].size();//number of wks
        vector<vector<int> > dp(N, vector<int>(K, INT_MIN));//the i'th city at week j'th
        int cur_max = days[0][0];
        dp[0][0] = days[0][0];
        for(int i = 1; i < N; ++i){
            if(flights[0][i]){
                dp[i][0] = days[i][0];
                cur_max = max(cur_max, dp[i][0]);
            }
        }
        for(int j = 1; j < K; ++j){//current wks
            for(int i = 0; i < N; ++i){//current position
                int tmp_max = INT_MIN;
                for(int k = 0; k < N; ++k){//previous destination
                    if(dp[k][j-1] == INT_MIN || (k != i && flights[k][i] == 0)) continue;
                    tmp_max = max(tmp_max, dp[k][j-1] + days[i][j]);
                }
                dp[i][j] = tmp_max;
                cur_max = max(cur_max, dp[i][j]);
            }
        }
        return cur_max;
    }
    };

Log in to reply
 

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