DMITRII’s Substack

Share this post

Leetcode daily # 21.04.2023

dmitriisamoilenko.substack.com

Leetcode daily # 21.04.2023

[879. Profitable Schemes]

DMITRII SAMOILENKO
Apr 21, 2023
Share

21.04.2023

879. Profitable Schemes hard

fun profitableSchemes(n: Int, minProfit: Int, group: IntArray, profit: IntArray): Int {
    val cache = Array(group.size) { Array(n + 1) { Array(minProfit + 1) { -1 } } }
    fun dfs(curr: Int, guys: Int, cashIn: Int): Int {
        if (guys < 0) return 0
        val cash = minOf(cashIn, minProfit)
        if (curr == group.size) return if (cash == minProfit) 1 else 0
        with(cache[curr][guys][cash]) { if (this != -1) return@dfs this }
        val notTake = dfs(curr + 1, guys, cash)
        val take = dfs(curr + 1, guys - group[curr], cash + profit[curr])
        val res = (notTake + take) % 1_000_000_007
        cache[curr][guys][cash] = res
        return res
    }
    return dfs(0, n, 0)
}

blog post

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/187

Intuition

For every new item, j we can decide to take it or not take it. Given the inputs of how many guys we have and how much cash already earned, the result is always the same: countj=notTakej(cash,guys)+takej(cash+profit[j],guys−group[j])

Approach

Do DFS and cache result in an array.

Complexity

  • Time complexity:
    O(n3)

  • Space complexity:
    O(n3)

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

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