Again Knapsack Variation | Easy to understand
TC - O(NM) n=size of piles, m=size of piles[i]\nJAVA\n\nclass Solution {\n    Integer dp[][];\n\n    public int maxValueOfCoins(List<List<Integer>> piles, int k
TC - O(N*M) n=size of piles, m=size of piles[i]\n**JAVA**\n```\nclass Solution {\n    Integer dp[][];\n\n    public int maxValueOfCoins(List<List<Integer>> piles, int k) {\n        this.dp = new Integer[piles.size() + 1][k + 1];\n        return solve(0, piles, k);\n    }\n\n    private int solve(int index, List<List<Integer>> p, int k) {\n        if (index >= p.size()) return 0;\n        int max = 0, sum = 0;\n        if (dp[index][k] != null) return dp[index][k];\n        //either dont take from that pile\n        max = Math.max(max, solve(index + 1, p, k));\n        for (int i = 0; i < p.get(index).size(); i++) {\n            sum += p.get(index).get(i);\n            //or take some certain prefix from that pile, if we can take that much elements.\n            if (k - (i + 1) >= 0) max = Math.max(max, sum + solve(index + 1, p, k - (i + 1)));\n        }\n        return dp[index][k] = max; // return max\n    }\n}\n```\n**CPP**\n```\nclass Solution {\n    public:\n        int dp[2001][2001] = { 0 };\n    int maxValueOfCoins(vector < vector < int >> & piles, int k) {\n        return solve(0, piles, k);\n    }\n    int solve(int index, vector < vector < int >> & piles, int k) {\n        if (index >= piles.size()) return 0;\n        if (dp[index][k] != 0) return dp[index][k];\n        int maxi = 0, sum = 0;\n        //either dont take from that pile\n        maxi = max(maxi, solve(index + 1, piles, k));\n        for (int i = 0; i < piles[index].size(); i++) {\n            sum += piles[index][i];\n            //or take some certain prefix from that pile, if we can take that much elements.\n            if (k - (i + 1) >= 0) maxi = max(maxi, sum + solve(index + 1, piles, k - (i + 1)));\n        }\n        return dp[index][k] = maxi;\n    }\n};\n```
['Memoization']