C#: DP, Recursion
Intuition\nUse DP and recursion.\n\n# Approach\nCreate the method\n\nprivate int MaxValueOfCoins((int index, int k) key, Dictionary<(int index, int k), int> dic
# Intuition\nUse DP and recursion.\n\n# Approach\nCreate the method\n```\nprivate int MaxValueOfCoins((int index, int k) key, Dictionary<(int index, int k), int> dic, IList<IList<int>> piles)\n```\n, where\n- (int index, int k) key contains the index of a current pile and k - the number of coins\n- Dictionary<(int index, int k), int> dic is a dictionary with a result for a certain key\n- IList<IList<int>> piles is an initial piles\nCall this method recursively.\n# Complexity\n- Time complexity:\n$$O(sum(len(piles[i])))$$\n\n- Space complexity:\n$$O(sum(len(piles[i])))$$\n\n# Code\n```\npublic class Solution {\n    public int MaxValueOfCoins(IList<IList<int>> piles, int k) {\n        var rs = MaxValueOfCoins((0, k), new Dictionary<(int index, int k), int>(), piles);\n        return rs;\n    }\n    private int MaxValueOfCoins((int index, int k) key, Dictionary<(int index, int k), int> dic, IList<IList<int>> piles)\n    {\n        if (piles.Count <= key.index || key.k <= 0) return 0;\n        if (dic.ContainsKey(key)) return dic[key];\n        var rs = MaxValueOfCoins((key.index + 1, key.k), dic, piles);\n        var sum = 0;\n        for (int i = 0; i < Math.Min(piles[key.index].Count, key.k); i++)\n        {\n            sum += piles[key.index][i];\n            var rs0 = sum + MaxValueOfCoins((key.index + 1, key.k - (i + 1)), dic, piles);\n            if (rs < rs0) rs = rs0;\n        }\n        if (!dic.ContainsKey(key)) dic.Add(key, rs);\n        return rs;\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'C#']