Easy to understand Recursive DP |Memorization✅
\n# Complexity\n- Time complexity:\n- O(N^2)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:\n- O(N^2)\n Add your space complexity here, e.g.
\n# Complexity\n- Time complexity:\n- O(N^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n- O(N^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n\nvector<vector<long long> > dp;\nvector<pair<long long,long long> > arr;\nlong long f(int i,int k){\nif(i>=arr.size())return 0;\nif(arr.size()-i<k)return -1e16; //If time remains more than number of elements\n\nif(dp[i][k]!=-1)return dp[i][k];\n\nlong long int t=-1e16;\nif(k>0)\nt= arr[i].first*k+arr[i].second+f(i+1,k-1);\n\n\nlong long int nt=f(i+1,k);\n\nreturn dp[i][k]=max(t,nt);\n\n}\nclass Solution {\npublic:\n\n\n    int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {\n        int n=nums1.size();\n        arr.clear();\ndp=vector<vector<long long> >(n+1,vector<long long>(n+1,-1));\n        for(int i=0;i<nums1.size();i++){\n            arr.push_back({nums2[i],nums1[i]});\n        }\n        sort(arr.rbegin(),arr.rend());\n\n        for(int i=0;i<=n;i++){\n                long long total=0;\n                for(int j=0;j<nums2.size();j++){\n                    total+=arr[j].first*i+ arr[j].second;\n                }\n            long long t=f(0,i);\n\n            if(total-t<=x){\n                return i;\n            }\n        }\n        return -1;\n    }\n};\n```
['C++']