C++ | ✅ Top Down DP Linear Space Complexity |  ✅ Bottom Up DP
Top Down DP linear space\n\nclass Solution {\n\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        \n        int n = piles.size();\n
# Top Down DP linear space\n```\nclass Solution {\n\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        \n        int n = piles.size();\n        vector<int> dp(k + 1);\n        dp[0] = 0;\n\n        for(int j = 1; j <= k; j++)\n            dp[j] = dp[j - 1] + (j - 1 < piles[n - 1].size() ? piles[n - 1][j - 1] : 0);\n        \n        for(int i = n - 2; i >= 0; i--)\n        {\n            vector<int> _dp(k + 1);\n            _dp[0] = 0;\n            for(int j = 1; j <= k; j++)\n            {\n                int preSum = 0;\n                int currMax = dp[j];\n                for(int x = 1; x <= j && x - 1 < piles[i].size(); x++)\n                {\n                    preSum += piles[i][x - 1];\n                    currMax = max(currMax, preSum + dp[j - x]);\n                }\n                _dp[j] = currMax;\n            }\n            dp.swap(_dp);\n        }\n\n        return dp[k];\n    }\n};\n\n```\n\n\n# Bottom Up DP\n```\n\nclass Solution {\n\n    int DFS(int index, int k, vector<vector<int>>& piles, vector<vector<int>> &dp)\n    {\n        if(index >= piles.size() || k == 0)\n            return 0;\n\n        if(dp[index][k] != -1)\n            return dp[index][k];\n\n        int ret = 0;\n        int preSum = 0;\n        \n        // completely ignore the current pile\n        ret = DFS(index + 1, k, piles, dp);\n\n        // try to add more and more coins from current pile and then move on\n        for(int i = 0; i < piles[index].size() && k - i - 1 >= 0; i++)\n        {\n            preSum += piles[index][i];\n            ret = max(ret, preSum + DFS(index + 1, k - i - 1, piles, dp));\n        }\n\n        return dp[index][k] = ret;\n    }\n\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        \n        vector<vector<int>> dp(piles.size(), vector<int>(k + 1, -1));\n        return DFS(0, k, piles, dp);\n    }\n};\n```
['C++']