🏆SPACE OPTIMISED - 💯TABULATION - ✅MEMOIZATION - ❗️RECURSION
Intuition\nThe problem is to maximize the sum of k coins collected from n piles of coins, where each pile has a different number of coins. The constraint is tha
# Intuition\nThe problem is to maximize the sum of k coins collected from n piles of coins, where each pile has a different number of coins. The constraint is that you can only take coins from the top of each pile. The given solution uses a depth-first search (DFS) approach to explore all possible choices of taking coins from different piles and computes the maximum sum of coins that can be collected.\n\n<hr>\n\n# Approach\nThe solution is implemented using a recursive function `helper()` which takes three parameters: `idx` (the current pile index), `coins` (the number of coins left to collect), and `piles` (the 2D vector of piles with coins).\n\nThe base case for the recursion is when the current pile index `idx` reaches the total number of `piles`. In this case, the function `returns 0`, as no more coins can be collected.\n\nThe main logic is divided into two cases:\n1. Not taking any coins from the current pile, in which case we move to the next pile by calling the `helper()` function with `idx + 1` and the same number of coins left to collect.\n2. Taking some coins from the current pile. In this case, we iterate through the coins in the current pile, taking at most `min(n, coins)` coins, where n is the total number of coins in the current pile. For each coin taken, we add its value to the `curr_total`, and then call the `helper()` function for the next pile with `idx + 1` and the updated number of coins left to collect `(coins - i - 1)`. We keep track of the maximum total coins collected in `max_total`.\n\nIn the end, the helper function returns `max_total` which is the maximum sum of coins that can be collected by considering all possible choices of taking coins from the current pile and subsequent piles.\n\nThe main function `maxValueOfCoins()` initiates the recursion by calling the `helper()` function with `idx = 0` (starting pile) and `coins = k` (the total number of coins to collect).\n<hr>\n\n# Implementations\n\n## Recursion - _Time Limit Exceeded_ \u203C\uFE0F\n```\nclass Solution {\nprivate:\n    int helper(int idx, int coins, vector<vector<int>>& piles) {\n        //Base case\n        if(idx == piles.size()) {\n            return 0;\n        }\n\n        //Explore all paths\n        int n = piles[idx].size();\n\n        //Path 1 - Not take any coin from the current pile\n        int max_total = helper(idx + 1, coins, piles);\n\n        //Path 2 - Take (i + 1) number of coins from the current pile\n        int curr_total = 0;\n        for(int i = 0; i < min(n, coins); i++) {\n            curr_total += piles[idx][i];\n            int next_total = helper(idx + 1, coins - i - 1, piles);\n            max_total = max(max_total, curr_total + next_total);\n        }\n        return max_total;\n    }\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        return helper(0, k, piles);\n    }\n};\n```\n\nIf `k` is the number of coins to collect, `m` is the number of piles and `n` is the total number of coins in all piles then:\n- **Time complexity:** $$O(k^n)$$\n\n- **Space complexity:** $$O(k * m)$$\n<hr>\n\n## Memoization (Top-Down) - _Accepted_ \u2705\nIt can be clearly seen from the recursive approcah that we are doing a lot of repeated work and there are overlapping sub-problems hence we can use dynamic programming to optimise out recursive approach. So let us memoize our recursion.\n```\nclass Solution {\nprivate:\n    int helper(int idx, int coins, vector<vector<int>>& piles, vector<vector<int>>& dp) {\n        //Base case\n        if(idx == piles.size()) {\n            return 0;\n        }\n        if(dp[idx][coins] != -1) {\n            return dp[idx][coins];\n        }\n\n        //Explore all paths\n        int n = piles[idx].size();\n\n        //Path 1 - Not take any coin from the current pile\n        int max_total = helper(idx + 1, coins, piles, dp);\n\n        //Path 2 - Take (i + 1) number of coins from the current pile\n        int curr_total = 0;\n        for(int i = 0; i < min(n, coins); i++) {\n            curr_total += piles[idx][i];\n            int next_total = helper(idx + 1, coins - i - 1, piles, dp);\n            max_total = max(max_total, curr_total + next_total);\n        }\n        return dp[idx][coins] = max_total;\n    }\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        int n = piles.size();\n        vector<vector<int>> dp(n + 1, vector<int>(k + 1, -1));\n        return helper(0, k, piles, dp);\n    }\n};\n```\n\nIf `k` is the number of coins to collect, `m` is the number of piles and `n` is the total number of coins in all piles then:\n- **Time complexity:** $$O(k * n)$$\n\n- **Space complexity:** $$O(k * m)$$\n<hr>\n\n## Tabulation (Bottom-Up) - _Accepted_ \u2705\u2705\nLet us now tabulise the memoization solution that we did above.\n```\nclass Solution {\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        int m = piles.size();\n        vector<vector<int>> dp(m + 1, vector<int>(k + 1, 0));\n        for(int idx = m - 1; idx >= 0; idx--) {\n            for(int coins = 1; coins <= k; coins++) {\n                //Explore all paths\n                int n = piles[idx].size();\n\n                //Path 1 - Not take any coin from the current pile\n                int max_total = dp[idx + 1][coins];\n\n                //Path 2 - Take (i + 1) number of coins from the current pile\n                int curr_total = 0;\n                for(int i = 0; i < min(n, coins); i++) {\n                    curr_total += piles[idx][i];\n                    int next_total = dp[idx + 1][coins - i - 1];\n                    max_total = max(max_total, curr_total + next_total);\n                }\n                dp[idx][coins] = max_total;                \n            }\n        }\n        return dp[0][k];\n    }\n};\n```\n\nIf `k` is the number of coins to collect, `m` is the number of piles and `n` is the total number of coins in all piles then:\n- **Time complexity:** $$O(k * n)$$\n\n- **Space complexity:** $$O(k * m)$$\n<hr>\n\n## Space Optimised Tabulation - _Accepted_ \u2705\u2705\u2705\nFrom the above tabulation code we can observe that the current pile `(dp[idx])` is always dependant on the next pile `(dp[idx + 1])`. So why not just keep 2 vectors of size `k + 1` each, one for `dp[idx]` and one for `dp[idx + 1]`. In this way we can save a lot of space by just computing two rows of the dp table at any instant instead of the entire `k x n` grid.\n```\nclass Solution {\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        int m = piles.size();\n        vector<int> curr(k + 1), next(k + 1, 0);\n        for(int idx = m - 1; idx >= 0; idx--) {\n            for(int coins = 1; coins <= k; coins++) {\n                //Explore all paths\n                int n = piles[idx].size();\n\n                //Path 1 - Not take any coin from the current pile\n                int max_total = next[coins];\n\n                //Path 2 - Take (i + 1) number of coins from the current pile\n                int curr_total = 0;\n                for(int i = 0; i < min(n, coins); i++) {\n                    curr_total += piles[idx][i];\n                    int next_total = next[coins - i - 1];\n                    max_total = max(max_total, curr_total + next_total);\n                }\n                curr[coins] = max_total;                \n            }\n            next = curr; //Make next = current for the next iteration\n        }\n        return next[k];\n    }\n};\n```\n\nIf `k` is the number of coins to collect, `m` is the number of piles and `n` is the total number of coins in all piles then:\n- **Time complexity:** $$O(k * n)$$\n\n- **Space complexity:** $$O(k)$$\n<hr>\n\n\uD83D\uDE4F **_If you like the entire explanation and all the implementations I showed, please do take a moment to upvote this post._** \uD83D\uDE4F
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']