✅ Easy DP Solution/Approach Explained 📝 | Beginner Friendly
Intuition\nThe intuition here is to understand that when we are on any currentPile we have two choices\n- either to exclude that pile and move on to next one or
# Intuition\nThe intuition here is to understand that when we are on any currentPile we have two choices\n- either to exclude that pile and move on to next one or\n- pick from currentPile one or two or three coins and so on till <= K(coinsLeft to pick) and currentPile is not exhausted of coins and then move on to new pile if coins are left\n\nNow when we try to solve with above approach, we see that there are repeating sub problems so we will go ahead and store results of repeating subproblems in a 2D DP array.\n\nDP[i][j] represent the max-value of coins(or sum) from j coins, when we are on ith pile.\n\n---\n\n\n# Approach\n1) We declare dp[n+1][k+1], we need to intialise DP with some variable so that we know if we have solved that subproblem so either intialise all elements *by -1* or i have made *dp = new Integer[][]* so that by default it is intialised *to null values*.\n\n2) Following top down approach we start iterating from last pile\n- check base conditions\n- return if we have already solved for that case already\n\n3) If above coditions don\'t pass then we calcualte what is coinPickLimit\n```\nint coinsPickLimit = Math.min(coinsLeft, piles.get(currentPile).size());\n```\nminmium we are taking since the each piles coins can get exhausted if we plan to take multiple coins from it.\n\n4) for currentPile either we \n- exclude it and move on to next pile \n```\nint excludeCurrentPile = helper(piles, currentPile-1, coinsLeft);\n```\n- or we include the currentPile and take 1 or 2 or .. coins from it(so for loop), we calculate sum and move onto next pile. Each time we pick a coin from curretPile we add to sum and move on to next pile get the result, we can repeat this till cointsLeftLimit.\n\nSo we calculate all possiblities of currentPile if we take one coint move on to next pile, then if we took 2 coins from currentPile and moved on to next pile and so on\n\nNow we have both result from excludeCurrentPile, includeCurentPile we do\n```\nMath.max(includeCurentPile, excludeCurrentPile)\n```\nand set it to dp[currentPile][coinsLeft]\n\nTry dry the code with 3 piles you will get the idea and why dp is imp as we are reusing our results.\n\n---\n\n# Complexity\n- Time complexity:\nO(n*k) where n is the total number of coins in all the piles\n\n---\nHope it is easy to understand.\nLet me know if there is something unclear and i can fix it.\n\nOtherwise, please upvote if you like the solution, it would be encouraging\n\n----\n\n# Code\n```\nclass Solution {\n    private Integer dp[][];\n    private int helper(List<List<Integer>> piles, int currentPile, int coinsLeft){\n        if(currentPile<0 || coinsLeft == 0)\n            return 0;\n        if(dp[currentPile][coinsLeft]!=null)\n            return dp[currentPile][coinsLeft];\n\n        int coinsPickLimit = Math.min(coinsLeft, piles.get(currentPile).size());\n\n        //not including that currentPile, so coinsLeft remain same\n        int excludeCurrentPile = helper(piles, currentPile-1, coinsLeft);\n        \n        int includeCurentPile=0;\n        for(int j=0, sum=0; j<coinsPickLimit ; j++){\n            sum+= piles.get(currentPile).get(j);\n            //doing coinsLeft-(j+1) as we are starting from index 0 and coin picked cannot pe 0 if we pick it is > 0\n            includeCurentPile = Math.max(sum + helper(piles, currentPile-1, coinsLeft-(j+1)), includeCurentPile);\n        }\n        \n        int res = Math.max(includeCurentPile, excludeCurrentPile);\n        dp[currentPile][coinsLeft] = res;\n        return res;\n\n    } \n\n    public int maxValueOfCoins(List<List<Integer>> piles, int K) {\n        int n = piles.size();\n        dp = new Integer[n + 1][K + 1];\n        return helper(piles, n-1, K);\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Java']