題目網址：https://leetcode.cn/problems/profitable-schemes/

題意：集團里有 n 名員工, 他們可以完成各種各樣的工作創造利潤。

第 i 種工作會產生 profit[i] 的利潤, 它要求 group[i] 名成員共同參與。如果成員參與了其中一項工作, 就不能參與另一項工作。

選取一些工作, 這些工作需產生至少 minProfit 的利潤, 且工作的成員總數不得超過 n。

有多少種方案可以選擇？因為答案很大, 所以返回結果 mod $10^9 + 7$ 的值即可。

Solution 1：

想法：利用 DP, 本題有兩種容量, 因此使用三維 DP

1. 定義狀態：

  • 首先, 會在 group、profit 前先加上一個 0, 代表什麼元素都沒有的狀態
  • dp[i][j][k]：前 i 個工作中「恰好」選擇了 j 個員工, 並滿足利潤為「至少」為 k 的方案數

2. 得到轉移方程：

  • 第 i 個工作有「選 or 不選」兩種選擇：

    • 若不選, 則要用前 i - 1 個工作完成選擇 j 個員工, 並滿足最小利潤為 k
      ➔ dp[i][j][k] = dp[i - 1][j][k]

    • 若要選, 假設第 i 個工作需 person 個員工, 且能創造 earn 利潤。則前 i - 1 個工作需選擇 j - person 個員工, 且至少需創造 k - earn 利潤
      ➔ dp[i][j][k] = dp[i - 1][j - person][k - earn]

      • 由於我們定義的 dp[i][j][k] 是利潤「至少」為 k, 而不是利潤「恰好」為 k, 故上述的第三維應改為 max(0, k - earn) 而不是 k - earn
      • 理由：若 earn > k, 代表光是第 i 個工作的利潤就超過要求 k 了, 但我們題目要求的是「至少」, 也就是說如果要求利潤「至少」為 k, 則利潤為 k、k + 1、k + 2、… 也都是滿足條件的
      • e.g. 若 earn > k, 則應選擇第 i 個工作（假設沒超過人數上限）, 並把該方案數加到 dp[i][j - person][0] 中, 代表前 i - 1 個工作就算利潤為 0 也沒關係, 只要選了第 i 個工作就能滿足利潤至少為 k

      ➔ dp[i][j][k] = dp[i - 1][j - person][max(0, k - earn)]

3. 初始化：

  • dp[0][0][0]：當沒有工作時, 選擇 0 個員工, 並滿足利潤為「至少」為 0 的方案數為 1（什麼都不選也是一種方案）
    ➔ dp[0][0][0] = 1

題目要求的是所有工作中, 利潤至少為 minProfit, 且工作的成員總數「不得超過」n, 因此選擇的人數可以是 0、1、…、n, 故答案要對所有可能人數的方案數進行加總
➔ res = (res + dp[m][j][minProfit]), for 0 ≤ j ≤ n

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        const int m = group.size(), mod = 1e9 + 7;
        vector<vector<vector<int>>> dp(m + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1, 0)));

        dp[0][0][0] = 1;
        group.emplace(group.begin(), 0);
        profit.emplace(profit.begin(), 0);

        for (int i = 1; i <= m; ++i) { // task
            const int person = group[i], earn = profit[i]; // 第 i 個工作所需的員工數、產生的利潤

            for (int j = 0; j <= n; ++j) { // person
                for (int k = 0; k <= minProfit; ++k) { // profit
                    if (j < person) { // 第 i 個工作的人數超過上限 j, 則不選
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else { // 第 i 個工作的人數沒超過上限, 則選、不選的方案都得考慮
                        dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - person][max(0, k - earn)]) % mod;
                    }
                }
            }
        }

        // 所有工作中, 人數 ≤ n, 且利潤至少為 minProfit 的方案數加總
        int res = 0;
        for (int j = 0; j <= n; ++j) {
            res = (res + dp[m][j][minProfit]) % mod;
        }

        return res;
    }
};
  • time：$O(m \cdot n \cdot minProfit)$ ➔ for loop
  • space：$O(m \cdot n \cdot minProfit)$ ➔ dp

Solution 2：

想法：改進 Solution 1, 由於 dp[i][j][k] 只會用到上一列的狀態, 因此只需保存上一列的狀態即可

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        const int m = group.size(), mod = 1e9 + 7;
        vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1, 0));

        dp[0][0] = 1;
        group.emplace(group.begin(), 0);
        profit.emplace(profit.begin(), 0);

        for (int i = 1; i <= m; ++i) { // task
            const auto prevRow = dp; // 記住上一列
            const int person = group[i], earn = profit[i];

            for (int j = 0; j <= n; ++j) { // person
                for (int k = 0; k <= minProfit; ++k) { // profit
                    if (j < person) {
                        dp[j][k] = prevRow[j][k];
                    } else {
                        dp[j][k] = (prevRow[j][k] + prevRow[j - person][max(0, k - earn)]) % mod;
                    }
                }
            }
        }

        int res = 0;
        for (int j = 0; j <= n; ++j) {
            res = (res + dp[j][minProfit]) % mod;
        }

        return res;
    }
};
  • time：$O(m \cdot n \cdot minProfit)$ ➔ for loop
  • space：$O(n \cdot minProfit)$ ➔ dp