DMITRII’s Substack

Share this post

Leetcode daily # 15.04.2023

dmitriisamoilenko.substack.com

Discover more from DMITRII’s Substack

I post a problem that I solve every single day
Continue reading
Sign in

Leetcode daily # 15.04.2023

2218. Maximum Value of K Coins From Piles

DMITRII SAMOILENKO
Apr 15, 2023
Share this post

Leetcode daily # 15.04.2023

dmitriisamoilenko.substack.com
Share

[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/)

Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.

#### 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)

Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.

Share this post

Leetcode daily # 15.04.2023

dmitriisamoilenko.substack.com
Share
Previous
Next
Comments
Top
New

No posts

Ready for more?

© 2023 DMITRII SAMOILENKO
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing