Leetcode daily # 21.04.2023

[879. Profitable Schemes]

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

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)