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];
 }

使用了動(dòng)態(tài)規(guī)劃的方法。更多的串的問題可以利用較少字符串的問題的結(jié)果。要看當(dāng)前字符串能不能利用，就看對于每個(gè)(r,c)的rsts[r][c]能不能變成rsts[r-zeros][c-ones]+1 這里從右下角往左上角進(jìn)行改變，因?yàn)檎蝽樞驎?huì)讓一個(gè)字符串使結(jié)果改變兩次。
如果要用正向順序，要復(fù)制一份，再復(fù)制回去。