✅C++ || Recursion->Memoization->Tabulation || 01-Knapsack
Method -1 [Recursion]\n\n\n\nT->O(Expo) && S->O(m) [Recursion stack space]\n\n\tclass Solution {\n\t\tpublic:\n\t\t\tlong long f(int i,vector>& r, vector& st,in
# Method -1 [Recursion]\n\n![image](https://assets.leetcode.com/users/images/d60997d9-759c-4e09-9616-1f21c674c804_1664626133.0203228.png)\n\n**T->O(Expo) && S->O(m) [Recursion stack space]**\n\n\tclass Solution {\n\t\tpublic:\n\t\t\tlong long f(int i,vector<vector<int>>& r, vector<int>& st,int m){\n\t\t\t\tif(i>=m) return 0;\n\t\t\t\tint ind=lower_bound(st.begin(),st.end(),r[i][1])-st.begin();\n\t\t\t\tint pick=(r[i][1]-r[i][0]+r[i][2])+f(ind,r,st,m);\n\t\t\t\tint notpick=f(i+1,r,st,m);\n\t\t\t\treturn max(pick,notpick);\n\t\t\t}\n\n\t\t\tlong long maxTaxiEarnings(int n,vector<vector<int>>& r) {\n\t\t\t\tint m=r.size();\n\t\t\t\tsort(r.begin(),r.end());\n\t\t\t\tvector<int> st;\n\t\t\t\tfor(int i=0;i<m;i++) st.push_back(r[i][0]);\n\t\t\t\treturn f(0,r,st,m);\n\t\t\t}\n\t\t};\n\t\t\n# Method - 2 [Memoization]\t\n\n![image](https://assets.leetcode.com/users/images/c66fe624-f033-4564-81d7-13a572190508_1664626871.2777963.png)\n\n**T->O(m) && S->O(m) + O(m) [Recursion stack space]**\n\n\tclass Solution {\n\tpublic:\n\t\tlong long f(int i,vector<vector<int>>& r, vector<int>& st,int m,vector<long long>& dp){\n\t\t\tif(i>=m) return 0;\n\t\t\tif(dp[i]!=-1) return dp[i];\n\t\t\tint ind=lower_bound(st.begin(),st.end(),r[i][1])-st.begin();\n\t\t\tlong long pick=(r[i][1]-r[i][0]+r[i][2])+f(ind,r,st,m,dp);\n\t\t\tlong long notpick=f(i+1,r,st,m,dp);\n\t\t\treturn dp[i]=max(pick,notpick);\n\t\t}\n\n\t\tlong long maxTaxiEarnings(int n,vector<vector<int>>& r) {\n\t\t\tint m=r.size();\n\t\t\tsort(r.begin(),r.end());\n\t\t\tvector<int> st;\n\t\t\tfor(int i=0;i<m;i++) st.push_back(r[i][0]);\n\t\t\tvector<long long> dp(m,-1);\n\t\t\treturn f(0,r,st,m,dp);\n\t\t}\n\t};\n\t\n# Method -3 [Tabulation]\n\n![image](https://assets.leetcode.com/users/images/44e1fc0e-b034-4e1f-9f3e-ed6364d08c39_1664627161.968081.png)\n\n\n**T->O(m) && S->O(m)**\n\n\tclass Solution {\n\tpublic:\n\t\tlong long maxTaxiEarnings(int n,vector<vector<int>>& r) {\n\t\t\tint m=r.size();\n\t\t\tsort(r.begin(),r.end());\n\t\t\tvector<int> st;\n\t\t\tfor(int i=0;i<m;i++) st.push_back(r[i][0]);\n\t\t\tvector<long long> dp(m+1,0);\n\t\t\tfor(int i=m-1;i>=0;i--){\n\t\t\t\tint ind=lower_bound(st.begin(),st.end(),r[i][1])-st.begin();\n\t\t\t\tlong long pick=(r[i][1]-r[i][0]+r[i][2])+dp[ind];\n\t\t\t\tlong long notpick=dp[i+1];\n\t\t\t\tdp[i]=max(pick,notpick);\n\t\t\t}\n\t\t\treturn dp[0];\n\t\t}\n\t};\n
['Binary Search', 'Dynamic Programming', 'Recursion', 'Memoization', 'C', 'C++']