[C++] Simple Bottom-up DP
Solution:\n\nclass Solution {\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        int n=piles.size();\n        \n        // dp[i][j]
Solution:\n```\nclass Solution {\npublic:\n    int maxValueOfCoins(vector<vector<int>>& piles, int k) {\n        int n=piles.size();\n        \n        // dp[i][j] = maximum money after taking j coins from first i piles.\n        vector<vector<int> > dp(n+1, vector<int>(k+1, -2000000000));\n        \n        dp[0][0]=0;\n        \n        for(int i=0; i<n; i++){\n            for(int j=0; j<=k; j++){\n                \n                // do not take any coin from this pile.\n                dp[i+1][j]=max(dp[i+1][j], dp[i][j]);\n                \n                int sum=0, cnt=0;\n                for(int p: piles[i]){\n                    sum+=p;\n                    cnt++;\n                    if(j+cnt<=k)\n                        // take first cnt coins from this pile.\n                        dp[i+1][j+cnt]=max(dp[i+1][j+cnt], dp[i][j]+sum);\n                }\n            }\n        }\n        return dp[n][k];\n    }\n};\n```\n\nTime complexity: O(k * sum(piles[i].length))\nProof: In iterative solutions it is much easier to deduce the time complexity.\n```\nfor each pile:\n\tfor each k:\n\t\tfor each prefix of pile:\n```\nis equivalent to\n```\nfor each pile:\n\tfor each prefix of pile:\n\t\tfor each k:\n```\n\nO(piles[0].length * k + piles[1].length * k + ...... + piles[n-1].length * k) = O(k * sum(piles[i].length))
[]