<p>There are <code>n</code> <strong>piles</strong> of coins on a table. Each pile consists of a <strong>positive number</strong> of coins of assorted denominations.</p>

<p>In one move, you can choose any coin on <strong>top</strong> of any pile, remove it, and add it to your wallet.</p>

<p>Given a list <code>piles</code>, where <code>piles[i]</code> is a list of integers denoting the composition of the <code>i<sup>th</sup></code> pile from <strong>top to bottom</strong>, and a positive integer <code>k</code>, return <em>the <strong>maximum total value</strong> of coins you can have in your wallet if you choose <strong>exactly</strong></em> <code>k</code> <em>coins optimally</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/11/09/e1.png" style="width: 600px; height: 243px;" />
<pre>
<strong>Input:</strong> piles = [[1,100,3],[7,8,9]], k = 2
<strong>Output:</strong> 101
<strong>Explanation:</strong>
The above diagram shows the different ways we can choose k coins.
The maximum total we can obtain is 101.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
<strong>Output:</strong> 706
<strong>Explanation:
</strong>The maximum total can be obtained if we choose all coins from the last pile.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == piles.length</code></li>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= piles[i][j] &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= k &lt;= sum(piles[i].length) &lt;= 2000</code></li>
</ul>

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        # solution redone here
        # original solutions further below
        n = len(piles)

        dp = [-float('inf')] * (k + 1)
        dp[0] = 0
        for j in range(1, k + 1):
            if j > len(piles[0]):
                break
            dp[j] = dp[j - 1] + piles[0][j - 1]
        
        for i in range(1, n):
            # prefix_sum[x] will store the result of taking the coins from piles[i] upto
            # but NOT including index x. equivalently, the result of taking x coins from piles[i]
            # so prefix_sum[0] = 0 always since taking zero coins has zero value
            # note that after below, len(prefix_sum) = min( k+1, len(piles)+1 )
            prefix_sum = [0]
            for x in range(min(len(piles[i]), k)):
                prefix_sum.append(prefix_sum[-1] + piles[i][x])
            # now we construct new_dp
            # new_dp[j] will store the best value achievable if we take exactly j coins from the
            # piles upto and including index i
            # note that some indices j will be -infinity (which occurs when j > sum(piles[:i+1]))
            # also note that taking zero coins always has zero value
            # so we set new_dp[0] = 0
            new_dp = [-float('inf')] * (k + 1)
            new_dp[0] = 0
            for j in range(1, k + 1):
                res = 0
                for x in range(min(len(prefix_sum), j + 1)):
                    res = max(res, prefix_sum[x] + dp[j - x])
                new_dp[j] = res
            dp = new_dp
        return max(dp)

    #     """
    #     Solution 1:
    #
    #     Let dp[i, j] be the most money you can collect if the array is
    #     piles[0, 1 ... i] right endpoint inclusive, and if we collect
    #     j coins total.

    #     Then dp[i, j] = max_{x = 0, 1 ... j}(
    #         dp[i - 1, j - x] + sum(piles[i][0:x])
    #     ).

    #     This is because we withdraw x coins from the i-th pile and
    #     j - x coins from the piles before i-th pile.
    #     """
    #     n = len(piles)

    #     for i in range(n):
    #         partial_sums = self.compute_partial_sums(piles, i, k)
    #         if i == 0:
    #             prev = [partial for partial in partial_sums]
    #             while len(prev) < k:
    #                 prev.append(-1 * float("inf"))
    #         else:
    #             curr = [-1 * float("inf")] * k
    #             # use j + 1 total coins
    #             for j in range(k):
    #                 res = prev[j] # all j + 1 coins from piles before i
    #                 if j < len(partial_sums):
    #                     # all j + 1 coins from pile i
    #                     res = max(res, partial_sums[j])
    #                 for x in range(j):
    #                     #x=0 means use 1 coin from piles[i], j coins
    #                     # from piles less than i
    #                     # x=j-1 means j coins from piles[i], 1 coin
    #                     # from piles less than i
    #                     if x < len(partial_sums):
    #                         res = max(res, prev[j - 1 - x] + partial_sums[x])
    #                     else:
    #                         break
    #                 curr[j] = res
    #             prev = curr
    #     return prev[k - 1]
                    

    
    # def compute_partial_sums(self, piles, i, k):
    #     partial_sums, res = [], 0
    #     for j in range(min(k, len(piles[i]))):
    #         res += piles[i][j]
    #         partial_sums.append(res)
    #     return partial_sums

        # """Solution 2:"""
        # n = len(piles)
        # seen = {}
        # def dp(state, left_to_pick):
        #     if left_to_pick == 0:
        #         return 0
        #     if tuple(state) in seen:
        #         return seen[tuple(state)]
            
        #     res = 0
        #     for i, idx_to_pick in enumerate(state):
        #         if idx_to_pick >= len(piles[i]):
        #             continue
        #         state[i] += 1
        #         res = max(res, piles[i][idx_to_pick] + dp(state, left_to_pick - 1))
        #         state[i] -= 1

        #     seen[tuple(state)] = res
        #     return res

        # initial_state = [0] * n
        # return dp(initial_state, k)
2081