Leetcode daily # 15.04.2023

2218. Maximum Value of K Coins From Piles

[2218. Maximum Value of K Coins From Piles](https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/description/) hard

fun maxValueOfCoins(piles: List<List<Int>>, k: Int): Int {
    val cache = Array(piles.size) { mutableListOf<Long>() }

        fun dfs(pile: Int, taken: Int): Long {
            if (taken >= k || pile >= piles.size) return 0
            if (cache[pile].size > taken) return cache[pile][taken]
            var max = dfs(pile + 1, taken)
            var sum = 0L
            for (j in 0..piles[pile].lastIndex) {
                val newTaken = taken + j + 1
                if (newTaken > k) break
                sum += piles[pile][j]
                max = maxOf(max, sum + dfs(pile + 1, newTaken))
            }
            cache[pile].add(max)
            return max
        }

        return dfs(0, 0).toInt()
    }

[blog post](https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/solutions/3418459/kotlin-dfs-cache/)

#### Join me on Telegram

https://t.me/leetcode_daily_unstoppable/181

#### Intuition

Given the current pile, we can assume there is an optimal maximum value of the piles to the right of the current for every given number of `k`.

#### Approach

We can cache the result by the keys of every `pile to taken`

#### Complexity

- Time complexity:

O(kn2)

- Space complexity:

O(kn2)