474. Ones and Zeroes

Medium

Description

給定一組二進位字串陣列 strs 和兩個整數 m（最多的 0 的數量）和 n（最多的 1 的數量），回傳最多能選幾個字串使得 0 的總數不超過 m、1 的總數不超過 n。

Example:

Input: strs = [“10”,“0001”,“111001”,“1”,“0”], m = 5, n = 3 Output: 4 (選 “10”, “0001”, “1”, “0”)

Intuition#

二維背包問題：每個字串有兩個「重量」（0 的數量和 1 的數量），背包有兩個容量限制。

類似 0/1 背包，但有兩個維度的容量限制
dp[i][j] 表示最多用 i 個 0 和 j 個 1 時能選的最大字串數
對每個字串，逆序更新 DP 表

Approaches#

1: 3D DP#

概念: dp[k][i][j] 表示考慮前 k 個字串，使用最多 i 個 0 和 j 個 1 的最大子集大小。
時間複雜度: O(k * m * n)，k 為字串數量
空間複雜度: O(k * m * n)

class Solution {
    fun findMaxForm(strs: Array<String>, m: Int, n: Int): Int {
        val k = strs.size
        val dp = Array(k + 1) { Array(m + 1) { IntArray(n + 1) } }

        for (idx in 1..k) {
            val zeros = strs[idx - 1].count { it == '0' }
            val ones = strs[idx - 1].length - zeros
            for (i in 0..m) {
                for (j in 0..n) {
                    dp[idx][i][j] = dp[idx - 1][i][j]
                    if (i >= zeros && j >= ones) {
                        dp[idx][i][j] = maxOf(dp[idx][i][j], dp[idx - 1][i - zeros][j - ones] + 1)
                    }
                }
            }
        }
        return dp[k][m][n]
    }
}

⭐2: 2D DP（空間優化）#

概念: 壓縮掉字串維度，逆序遍歷容量以保證每個字串只使用一次。
時間複雜度: O(k * m * n)
空間複雜度: O(m * n)

class Solution {
    fun findMaxForm(strs: Array<String>, m: Int, n: Int): Int {
        val dp = Array(m + 1) { IntArray(n + 1) }

        for (s in strs) {
            val zeros = s.count { it == '0' }
            val ones = s.length - zeros
            for (i in m downTo zeros) {
                for (j in n downTo ones) {
                    dp[i][j] = maxOf(dp[i][j], dp[i - zeros][j - ones] + 1)
                }
            }
        }
        return dp[m][n]
    }
}

🔑 Takeaways#

Pattern: 二維 0/1 背包 — 兩個容量限制，物品價值為 1
關鍵技巧: 逆序遍歷兩個維度的容量；本質上是 0/1 背包的擴展，只是多了一個維度