Maximum Value of K Coins From Piles LeetCode solution in Python

1
class Solution:
2
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
3
        n = len(piles)
4
        prefixSum = []
5
        for i in range(n):
6
            temp = [0]
7
            for j in range(len(piles[i])):
8
                temp.append(temp[-1] + piles[i][j])
9
            prefixSum.append(temp)
10

11
        dp = [[0] * (k + 1) for _ in range(n)]
12
        for j in range(1, k + 1):
13
            if j < len(prefixSum[0]):
14
                dp[0][j] = prefixSum[0][j]
15

16
        for i in range(1, n):
17
            for j in range(1, k + 1):
18
                for l in range(len(prefixSum[i])):
19
                    if l > j:
20
                        break
21
                    dp[i][j] = max(dp[i][j], prefixSum[i][l] + dp[i - 1][j - l])
22
        return dp[n - 1][k]