Simple DP with Explanation || C++ Code
dp[i] stores the max earning if we start from i.\nSay we have n people want to go from point i to any other point > i.\nNow we have two options -\ni) We take an
**dp[i]** stores the max earning if we start from i.\nSay we have n people want to go from point i to any other point > i.\nNow we have two options -\ni) We take any of the passenger from point i.\nii) We don\'t take any passenger.\n\nIf we take jth passenger then dp[i] will be \n**dp[i]= end point of jth passenger - start point of jth passenger + tip given by the jth passenger + dp[end point of jth passenger]**\n```\n#define ll long long int \nclass Solution {\npublic:\n    long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {\n        vector<ll> dp(n+1,0);\n        unordered_map<ll,vector<vector<ll>>> startTime;\n        \n        for(auto x: rides)\n        {\n            ll start=x[0];\n            ll end=x[1];\n            ll tip=x[2];\n            \n            startTime[start].push_back({end,tip});\n        }\n    \n        for(int i=n-1;i>=1;i--)\n        {\n            dp[i]=dp[i+1];\n            if(startTime[i].size()==0)continue;\n            for(auto x: startTime[i])\n            {\n                    ll end=x[0];\n                    ll tip=x[1];\n                    \n                    dp[i]=max(dp[i],end-i+tip+dp[end]);\n            }\n        }\n        \n        \n        return dp[1];\n    }\n};\n```
[]