C++ easy DP solution


  • 0
    M
        int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
            int n=flights.size(), k=days[0].size(), res=0;
            vector<vector<int>> dp(n, vector<int>(k, -1));
            dp[0][0]=days[0][0];
            for(int i=1;i<n;i++) {
                if(flights[0][i]==1) dp[i][0]=days[i][0];
            }
            for(int i=1;i<k;i++) {
                for(int j=0;j<n;j++) {
                    for(int m=0;m<n;m++) {
                        if((flights[m][j]==1||m==j)&&dp[m][i-1]!=-1) dp[j][i]=max(dp[m][i-1]+days[j][i], dp[j][i]);
                    }
                }
            }
            for(int i=0;i<n;i++) res=max(res, dp[i][k-1]);
            return res;
        }

Log in to reply
 

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