879

879. Profitable Schemes (Hard)

There is a group of n members, and a list of various crimes they could commit. The ith crime generates a profit[i] and requires group[i] members to participate in it. If a member participates in one crime, that member can't participate in another crime.

Let's call a profitable scheme any subset of these crimes that generates at least minProfit profit, and the total number of members participating in that subset of crimes is at most n.

Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation: To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.

Example 2:

Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation: To make a profit of at least 5, the group could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).

 

Constraints:

• 1 <= n <= 100
• 0 <= minProfit <= 100
• 1 <= group.length <= 100
• 1 <= group[i] <= 100
• profit.length == group.length
• 0 <= profit[i] <= 100

Companies:
Google

Related Topics:
Array, Dynamic Programming

Solution 1. Top-down DP

Let dp(i,j,k) be the number of profitable schemas using crimes whose indexes are in range [i, M), j member allowance, and k as profit goal (i.e. minimum total profit).

dp(i, j, k) = dp(i+1, j, k)                    // skip crime `i`
              dp(i+1, j-group[i], k-profit[i]) // use crime `i`

Special cases:

• dp(i, j, k) = 0 if j < 0 (no member allowance)
• If i == M, dp(i, j, k) = k <= 0 ? 1 : 0 (If profit goal <= 0, it's achievable)

Note that when k < 0, we need to do k = max(0, k) because negative profit goal has the same schema as 0 profit goal.

// OJ: https://leetcode.com/problems/profitable-schemes/
// Author: github.com/lzl124631x
// Time: O(MNP) where `M` is the number of crimes, `N` is the number of members, and `P` is `minProfit`
// Space: O(MNP)
class Solution {
public:
    int profitableSchemes(int N, int minProfit, vector<int>& group, vector<int>& profit) {
        long mod = 1e9 + 7, M = group.size(), dp[101][101][101] = {}; // crime, members, profit
        memset(dp, -1, sizeof(dp));
        function<long(int, int, int)> dfs = [&](int i, int j, int k) {
            if (j < 0) return 0L; // If we don't have enough members, return 0
            if (i == M) return k <= 0 ? 1L : 0L; // If the profit goal is not positive, it's achievable and we return 1; otherwise, return 0.
            k = max(0, k); // Negative profit goal is the same as 0 profit goal
            if (dp[i][j][k] != -1) return dp[i][j][k];
            return dp[i][j][k] = (dfs(i + 1, j, k) + dfs(i + 1, j - group[i], k - profit[i])) % mod; // skip crime `i` or pick crime `i`.
        };
        return dfs(0, N, minProfit);
    }
};

Solution 2. Bottom-up DP

// OJ: https://leetcode.com/problems/profitable-schemes/
// Author: github.com/lzl124631x
// Time: O(MNP)
// Space: O(MNP)
class Solution {
public:
    int profitableSchemes(int N, int minProfit, vector<int>& group, vector<int>& profit) {
        long mod = 1e9 + 7, M = group.size(), dp[101][101][101] = {}; // crime, members, profit
        for (int j = 0; j <= N; ++j) dp[0][j][0] = 1;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j <= N; ++j) {
                for (int k = 0; k <= minProfit; ++k) {
                    long val = dp[i][j][k];
                    if (j - group[i] >= 0)
                        val = (val + dp[i][j - group[i]][max(0, k - profit[i])]) % mod;
                    dp[i + 1][j][k] = val;
                }
            }
        }
        return dp[M][N][minProfit];
    }
};

Since dp[i+1] values only depends on dp[i], we can reduce the space complexity to O(NP).

// OJ: https://leetcode.com/problems/profitable-schemes/
// Author: github.com/lzl124631x
// Time: O(MNP)
// Space: O(NP)
class Solution {
public:
    int profitableSchemes(int N, int minProfit, vector<int>& group, vector<int>& profit) {
        long mod = 1e9 + 7, M = group.size(), dp[101][101] = {}, tmp[101][101] = {}; // crime, members, profit
        for (int j = 0; j <= N; ++j) dp[j][0] = 1;
        for (int i = 0; i < M; ++i) {
            swap(tmp, dp);
            for (int j = 0; j <= N; ++j) {
                for (int k = 0; k <= minProfit; ++k) {
                    long val = tmp[j][k];
                    if (j - group[i] >= 0)
                        val = (val + tmp[j - group[i]][max(0, k - profit[i])]) % mod;
                    dp[j][k] = val;
                }
            }
        }
        return dp[N][minProfit];
    }
};