LeetCode|LeetCode 474 LeetCode474

LeetCode 474 474 Ones and Zeroes
类似 0 1 背包问题的问题

int solve(vector &strs, int m, int n) { vector> rsts(m + 1, vector(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]; }

【LeetCode|LeetCode 474】使用了动态规划的方法。更多的串的问题可以利用较少字符串的问题的结果。要看当前字符串能不能利用，就看对于每个(r,c)的rsts[r][c]能不能变成rsts[r-zeros][c-ones]+1 这里从右下角往左上角进行改变，因为正向顺序会让一个字符串使结果改变两次。
如果要用正向顺序，要复制一份，再复制回去。