✅C++ || EASY DP (Recursive + Memoization)
Code\n\nclass Solution {\n    #define ll long long\npublic:\n    int c(vector<vector<int>>& p,int i,int k,vector<vector<int>>&dp){\n        if(k==0)return 0;\n 
# Code\n```\nclass Solution {\n    #define ll long long\npublic:\n    int c(vector<vector<int>>& p,int i,int k,vector<vector<int>>&dp){\n        if(k==0)return 0;\n        if(i>=p.size())return 0;\n        if(dp[i][k]!=-1)return dp[i][k];\n        int ans=0;\n        int mx=c(p,i+1,k,dp);\n        for(int j=0;j<p[i].size();j++){\n            ans += p[i][j];\n            if(k>=j+1)\n           mx = max(mx,ans+c(p,i+1,k-j-1,dp));\n           else break;\n        }\n        dp[i][k]=mx;\n        return mx;\n    }\n    int maxValueOfCoins(vector<vector<int>>& p, int k) {\n        int n=p.size();\n        vector<vector<int>>dp(n,vector<int>(k+1,-1));\n        return c(p,0,k,dp);\n    }\n};\n```\n![upvote (2).jpg](https://assets.leetcode.com/users/images/6562a796-f88c-4354-91ae-9f672244bb39_1681546108.315926.jpeg)\n
['Dynamic Programming', 'Prefix Sum', 'C++']