C++ DP solution | Intuitive
Approach\n Describe your approach to solving the problem. \nYou can watch Coding Mohan\'s YouTube video solution for this, it\'s really difficult to describe th
# Approach\n<!-- Describe your approach to solving the problem. -->\nYou can watch Coding Mohan\'s YouTube video solution for this, it\'s really difficult to describe the solution in a textual post for me.\nMy solution is inspired from his only.\n\n\n# Code\n```\nclass Solution {\npublic:\n\n    vector<int>a,b;\n\n    int dp[1001][1001];\n\n    int maxOp(int col, int ops){\n        if(ops==0)return 0;\n        if(col<0)return -1e5;\n\n        if(dp[col][ops]!=-1)return dp[col][ops];\n\n        //take\n        int op1 = a[col]+b[col]*ops + maxOp(col-1,ops-1);\n\n        //not-take\n        int op2 = maxOp(col-1,ops); \n\n        return dp[col][ops]=max(op1,op2);\n    }\n\n    int minimumTime(vector<int>& _a, vector<int>& _b, int x) {\n        vector<pair<int,int>>p;\n        for(int i=0;i<_a.size();i++){\n            p.push_back({_b[i],_a[i]});\n        }\n\n        sort(p.begin(),p.end());\n\n        for(int i=0;i<p.size();i++){\n            a.push_back(p[i].second);\n            b.push_back(p[i].first);\n        }\n\n        p.clear(), _a.clear(), _b.clear();\n\n        int n=a.size();\n\n        memset(dp,-1,sizeof(dp));\n\n        int asum=0,bsum=0;\n\n        for(int j=0;j<n;j++)\n        {\n            asum+=a[j];\n            bsum+=b[j];\n        }\n\n        for(int i=0;i<=n;i++){\n            int sum=asum+i*bsum;\n            if(sum-maxOp(n-1,i)<=x)return i;\n        }\n\n        return -1;\n    }\n};\n```
['C++']