題目網址：https://leetcode.cn/problems/ones-and-zeroes/

題意：給一二進制 string array strs 和兩整數 m 和 n。

給你 m 個 0 和 n 個 1, 求最多可以組成幾個 strs 中的 string。

Solution 1：

想法：利用 DP, 本題有兩種容量（0、1 數量）, 因此使用三維 DP

1. 定義狀態：

  • 首先, 會在 strs 前先加上一個 "", 代表什麼元素都沒有的狀態
  • dp[i][j][k]：strs[1:i] 中, 使用 j 個 0 和 k 個 1 最多所能組成的 string 個數

2. 得到轉移方程：

  • 假設 strs[i] 有 zeros 個 0 和 ones 個 1, 則每個 strs[i] 有兩種選擇（選 or 不選）

  • 若 zeros > j 或 ones > k, 則 strs[i] 必不能選（超過個數上限）
    ➔ dp[i][j][k] = dp[i - 1][j][k]

  • 若 zeros ≤ m 或 ones ≤ n：

    • 若 strs[i] 要選, 則 dp[i][j][k] = dp[i - 1][j - zeros][k - ones] + 1
    • 若 strs[i] 不選, 則 dp[i][j][k] = dp[i - 1][j][k]

3. 初始化：

  • dp[0][0][0]：當沒有元素時, 0 個 0、0 個 1 最多組成 0 的 string
  • 其餘皆初始成 0
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        const int len = strs.size();
        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));

        strs.emplace(strs.begin(), "");

        for (int i = 1; i <= len; ++i) {
            int zeros = 0, ones = 0;

            for (const auto& ch : strs[i]) {
                if (ch == '0') {
                    ++zeros;
                } else {
                    ++ones;
                }
            }

            for (int j = 0; j <= m; ++j) {
                for (int k = 0; k <= n; ++k) {
                    dp[i][j][k] = dp[i - 1][j][k]; // 先預設 strs[i] 不選（無法滿足下面條件）
                    if (j >= zeros && k >= ones) { // 若沒超過上限個數, 則挑兩者中最大的
                        dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - zeros][k - ones] + 1);
                    }
                }
            }
        }

        return dp[len][m][n];
    }
};
  • time：$O(len \cdot m \cdot n + L)$ ➔ for loop, len 是 strs 的長度, L 是所有 string 長度之和
    • $O(len \cdot m \cdot n)$：for loop
    • $O(L)$：計算所有 string 的 0、1 個數
  • space：$O(len \cdot m \cdot n)$ ➔ dp

Solution 2：

想法：改進 Solution 1, 因為 dp[i][j][k] 只會用到上一列的狀態, 因此只需保存上一列的狀態即可, 根本不需開到 $O(len \cdot m \cdot n)$ space

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        const int len = strs.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        strs.emplace(strs.begin(), "");

        for (int i = 1; i <= len; ++i) {
            int zeros = 0, ones = 0;

            for (const auto& ch : strs[i]) {
                if (ch == '0') {
                    ++zeros;
                } else {
                    ++ones;
                }
            }

            const auto prevRow = dp; // 紀錄上一列的狀態
            for (int j = zeros; j <= m; ++j) {
                for (int k = ones; k <= n; ++k) {
                    dp[j][k] = max(prevRow[j][k], prevRow[j - zeros][k - ones] + 1);
                }
            }
        }

        return dp[m][n];
    }
};
  • time：$O(len \cdot m \cdot n + L)$ ➔ len 是 strs 的長度, L 是所有 string 長度之和
    • $O(len \cdot m \cdot n)$：for loop
    • $O(L)$：計算所有 string 的 0、1 個數
  • space：$O(m \cdot n)$ ➔ dp