Skip to main content

ones-and-zeroes

474. Ones and Zeroes

0/1 背包問題,對於每個 subset,有取或不取兩個選擇。

Hint

2 維的 (m+1)(n+1)(m + 1) \cdot (n + 1) DP 陣列

對於每個狀態都有選,或不選兩個選擇

  • 不選:dp[i][j]
  • 選:dp[i - zeros][j - ones] + 1

狀態轉移:dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);

每個格子都是取最大的 subsets 的狀態

+ 1 代表的是加了這次的選擇

class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int maxSubset = 0;

vector<vector<int>> dp(m + 1, vector<int>(n + 1));

for (auto s : strs)
{
int zeros = 0, ones = 0;
for (auto c : s) {
c == '0' ? ++zeros : ++ones;
}

for (int i = m; i >= zeros; --i)
{
for (int j = n; j >= ones; --j)
{
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
}
};
  • T: O(LMN)O(L \cdot M \cdot N)
  • S: O(MN)O(M \cdot N)