PYTHON || easy solution with explanation || recursion with caching
Intuition\n Describe your first thoughts on how to solve this problem. \ndynamic programming problem \n# Approach\n Describe your approach to solving the proble
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\ndynamic programming problem \n# Approach\n<!-- Describe your approach to solving the problem. -->\n- we first skip all nodes to start from last assume i have 4 piles (try last piles , then try 3rd and last pile , etc)\n- with base case if i ==n or k ==0 return 0\n- in for loop i try all possible coins in cur pile to last pile in limit with k\n- cur_val save the value of cur try , ans res save max res of all tries \n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\no(n2)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\no(n)\n# Code\n```\nclass Solution(object):\n    def maxValueOfCoins(self, piles, k):\n        """\n        :type piles: List[List[int]]\n        :type k: int\n        :rtype: int\n        """\n        cache ={}\n        def dfs(i,k ):\n            if (i,k) in cache:\n                return cache[(i,k)]\n            if k==0 or i == len(piles):\n                return 0\n            # skip piles until reach end , then try all possible from last to first \n            dfs(i+1 , k) \n            res , cur_val = dfs(i+1 , k),0\n            for j in range(min(k , len(piles[i]))):\n                cur_val += piles[i][j]\n                # print(cur_val ,res )\n                res = max(res , cur_val + dfs(i+1 , k-j-1))\n            cache[(i,k)]=res\n            return cache[(i,k)]\n        return dfs(0,k)\n\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'Python', 'Python3']