LeetCode 474
474 Ones and Zeroes
類似 0 1 背包問題的問題
int solve(vector<string> &strs, int m, int n) {
vector<vector<int>> rsts(m + 1, vector<int>(n + 1));
for (auto &s:strs) {
int zeros = count(s.begin(), s.end(), '0');
int ones = s.size() - zeros;
for (int r = m; r >= zeros; r--)
for (int c = n; c >= ones; c--)
if (rsts[r - zeros][c - ones] + 1 > rsts[r][c])
rsts[r][c] = rsts[r - zeros][c - ones] + 1;
}
return rsts[m][n];
}
使用了動態(tài)規(guī)劃的方法凿蒜。更多的串的問題可以利用較少字符串的問題的結果。要看當前字符串能不能利用招驴，就看對于每個(r,c)的rsts[r][c]能不能變成rsts[r-zeros][c-ones]+1 這里從右下角往左上角進行改變篙程，因為正向順序會讓一個字符串使結果改變兩次。
如果要用正向順序别厘，要復制一份虱饿，再復制回去。
