"Maximum Earnings From Taxi" [C++ DP]- Easy Solution
C++ Easy Dynamic Programming Solution :-\nOur task is to choose passengers optimally such that total number of dollars will be Maximum. We are using a hashmap t
### C++ Easy Dynamic Programming Solution :-\nOur task is to choose passengers optimally such that total number of dollars will be **Maximum**. We are using a hashmap to keep track of all the destination points which have the same boarding point of the passengers. After that we are using Dynamic Programming to choose the optimal starting point and the optimal destination point to get the max profit.\n\n* **Code** :-\n```\nclass Solution {\npublic:\n    map<int,vector<pair<int,int>>> mpp;  // To store the destination points and total number of dollars\n    vector<long long> memo;\n    Solution(){\n        mpp.clear();  // Initializing the map\n        memo.resize(100005,-1);  // Initializing the vector with -1\n    }\n    long long dp(int idx,int n){\n        if(idx>n) return 0;  // The journey of the taxi ends\n        if(memo[idx]!=-1) return memo[idx];  // If this subproblem is already solved, directly getting the answer\n        long long ans=0;\n        for(auto x:mpp[idx]){\n            ans=max(ans,dp(x.first,n)+x.second);  // Determining which schedule should we take to get max profit\n        }\n\t\t// If there is no schedule at that starting point the ans will be 0 and proceed to the next condition\n        ans=max(ans,dp(idx+1,n));  // Checking if we get the max profit by not taking the particular starting point\n        // cout<<idx<<" "<<ans<<endl;\n        return memo[idx]=ans;\n    }\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        for(auto x: rides){\n            mpp[x[0]].push_back({x[1],(x[1]-x[0]+x[2])});  // Storing the destination points and total number of dollars of the passenges of same starting point.\n        }\n        return dp(1,n);  // Finally we get our answer :)\n    }\n\t// Happy Coding\n};\n```\n\n* Time Complexity :- O(n*logn)\n* Space Complexity :- O(n)\n\nIf you like the blog make sure you hit the Upvote button. Thanks in Advance :)\n
['Dynamic Programming']