LeetCode Entry
2218. Maximum Value of K Coins From Piles
We can cache the result by the keys of every pile to taken
2218. Maximum Value of K Coins From Piles 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()
}
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(kn^2)\)
- Space complexity: \(O(kn^2)\)