Recursion to Space Optimized DP | Java explained solution | Easy to understand
\nThis question is a variation of 0/1 Unbounded Knapsack. Here we are allowed to pick coins any no. of times with 2 included constraints. \n- These picking up o
\nThis question is a variation of 0/1 Unbounded Knapsack. Here we are allowed to pick coins any no. of times with 2 included constraints. \n- These picking up of coins from a particular pile cannot exceed k\n- The coins in a particular pile are of different denomination\n\nIf these two constraints are removed the question is basic 0/1 Unbounded knapsack. So, similarly we have two options to go for.\n- either to not pick any coin from a pile\n- or pick 1 to k coins from a pile\n\nRecursion\n```\n public int maxValueOfCoins(List<List<Integer>> piles, int k) {\n        int n=piles.size();\n        return solve(piles,n,k);\n    }\n    \n    public int solve(List<List<Integer>> piles,int i,int k){\n        if(k==0)return 0;\n        if(i==0)return 0;\n        int best=solve(piles,i-1,k);\n        List<Integer> pile=piles.get(i-1);\n        int sum=0;\n        for(int x=0;x<Math.min(k,pile.size());x++){\n            sum+=pile.get(x);\n            best=Math.max(best,+solve(piles,i-1,k-(x+1)));\n        }\n        return best;\n    }\n```\nTC= Exponential (For every pile we have either to pick upto k coins or not pick at all)\nSC= O(nk)\n\nRecursion with Memoization\n```\n public int maxValueOfCoins(List<List<Integer>> piles, int k) {\n        int n=piles.size();\n\t\tint[][] dp=new int[n+1][k+1];\n        for(int i=0;i<=n;i++)\n\t\t\tArrays.fill(dp[i],-1);\n        return solve(piles,n,k,dp);\n    }\n    \n    public int solve(List<List<Integer>> piles,int i,int k,int[][] dp){\n\t\tif(k==0)return 0;\n        if(i==0)return 0;\n\t\tif(dp[i][k]!=-1)return dp[i][k];\n        int best=solve(piles,i-1,k,dp);\n        List<Integer> pile=piles.get(i-1);\n        int sum=0;\n        for(int x=0;x<Math.min(k,pile.size());x++){\n            sum+=pile.get(x);\n            best=Math.max(best,+solve(piles,i-1,k-(x+1),dp));\n        }\n        return dp[i][k]= best;\n    }\n```\nTC= O(nk)\nSC= O(nk)+O(nk)\n\nTabulation DP\n```\n    \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        for(int i=0;i<=n;i++){\n            for(int j=0;j<=k;j++){\n                if(i==0 || j==0)dp[i][j]=0;\n                else{\n                    int best=dp[i-1][j];\n                    List<Integer> pile=piles.get(i-1);\n                    int sum=0;\n                    for(int x=0;x<Math.min(j,pile.size());x++){\n                        sum+=pile.get(x);\n                        best=Math.max(best,sum+dp[i-1][j-(x+1)]);\n                    }\n                    dp[i][j]= best;\n                }\n            }\n        }\n        return dp[n][k];\n    }\n```\nTC= O(nk)\nSC= O(nk)\n\nTabulation DP with Space optimization\n```\n public int maxValueOfCoins(List<List<Integer>> piles, int k) {\n        int n=piles.size();\n        int[] prev=new int[k+1];\n        for(int i=0;i<=n;i++){\n            int[] curr=new int[k+1];\n            for(int j=0;j<=k;j++){\n                if(i==0 || j==0)curr[j]=0;\n                else{\n                    int best=prev[j];\n                    List<Integer> pile=piles.get(i-1);\n                    int sum=0;\n                    for(int x=0;x<Math.min(j,pile.size());x++){\n                        sum+=pile.get(x);\n                        best=Math.max(best,sum+prev[j-(x+1)]);\n                    }\n                    curr[j]= best;\n                }\n            }\n            prev=curr;\n        }\n        return prev[k];\n    }\n```\nTC= O(nk)\nSC= O(2k)=O(k)\n\nHope you liked the solution. If yes, do upvote. Thanks!
['Dynamic Programming', 'Recursion', 'Java']