Easy || C++ || DP
Intuition\nSome point that are directly hit to mind.\nif we take piles[i][j] coin we need to take all the coins above index j in that i pile.\n\nfrom above we c
# Intuition\nSome point that are directly hit to mind.\n`if we take piles[i][j] coin we need to take all the coins above index j in that i pile.`\n\n`from above we can conlude that instead of taking one by one coin from a given row we take in bunch`\n\n# Approach\n\n`TRY ALL POSSIBLE WAYS`\n\n`To take bunch of coins we used presum of all indivisual piles of coins`\n```\nfor(int i=0;i<n;i++){\n  int su=0;\n    for( int a : pp[i]){\n        pre[i].push_back(su);\n        su+=a;\n    }\n    pre[i].push_back(su);\n}\n```\nZero index means we are not taking any coin from that pile.\n\nNow we can take connect whole problem to 0/1 knapsack\n\nNeed to select a index from every presum of piles of coins and add to aur answer , and eqaully dicreasing count of k.\n\n`NOW USE DP`\n\nHere we can easily see only current number of pile and count remaning to add (k) is changing in our recursive code.\n\nso lets make 2D DP vector to store. \n\n# Complexity\n- Time complexity:\nO(N2)    {mota mota}\n\n- Space complexity:\nO(N*K)\n\n# Code\n```\nclass Solution {\npublic:\n\n    int fun(vector<vector<int>> &pp , int cu , int k, vector<vector<int>> &dp ){\n        if(cu>=pp.size()) return 0;\n        if(dp[cu][k] != -1 ) return dp[cu][k];\n        int mx=0;\n        for(int i=0;i<pp[cu].size();i++){\n            if(k-i>=0) mx = max(mx , pp[cu][i]+fun(pp,cu+1,k-i,dp));\n        }\n        return dp[cu][k] = mx;\n    }\n\n    int maxValueOfCoins(vector<vector<int>>& pp, int k) {\n        int  n = pp.size();\n        vector<vector<int>> pre(n);\n        vector<vector<int>> dp(n+2,vector<int>(k+2,-1));\n        for(int i=0;i<n;i++){\n            int su=0;\n            for( int a : pp[i]){\n                pre[i].push_back(su);\n                su+=a;\n            }\n            pre[i].push_back(su);\n        }\n        return fun(pre,0,k,dp);\n    }\n};\n```
['C++']