[Java] Bottom up DP with clear explanation and code
Either pick all k from previous piles, or choose j from current pile and pick k-j from previous piles\nRecurrence relation:\nf(n,k) represents the max sum of co
Either pick all k from previous piles, or choose j from current pile and pick k-j from previous piles\n**Recurrence relation**:\n`f(n,k)` represents the max sum of coins collected from first `n` piles and choosing `k` top coins.\n```\nf(n,k) = max(\n\t\t\tf(n-1,k) // pick k from previous n-1 piles\n\t\t\t,max(f(n-1,k-j-1)+sum(0 to j) for j = 0 to min(k,p[n-1].size())) // pick j+1 from current pile and k-j-1 from previous n-1 piles\n\t\t)\n```\nif k = 0, i.e. you can\'t pick any coin then ans = 0\nif n = 0, i.e. you don\'t have any piles then ans = 0\n**Base cases** :\n`f(0,k) = 0`\n`f(n,0) = 0`\n\n```\n/*\nf(i,k) = max(f(i-1,k),max(f(i-1,k-j-1)+sum(j) for j = 0 to max(k,p[i-1].length)))\nf(i,0) = 0\nf(0,k) = 0\n*/\nclass Solution {\n    public int maxValueOfCoins(List<List<Integer>> piles, int K) {\n        int n = piles.size();\n        int[][] dp = new int[n+1][K+1];\n        \n        for(int i = 1; i <= n; i ++) {\n            for(int k = 1; k <= K; k ++) {\n                dp[i][k] = dp[i-1][k];\n                int sum = 0;\n                int picked = 1;\n                for(int v: piles.get(i-1)) {\n                    if(k-picked < 0) {\n                        break;\n                    }\n                    sum += v;\n                    dp[i][k] = Math.max(dp[i][k], dp[i-1][k-picked]+sum);\n                    picked ++;\n                }\n            }\n        }\n        return dp[n][K];\n    }\n}\n```
['Dynamic Programming', 'Java']