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

• 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;
}
};``````

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