Open
Description
在计算机界中，我们总是追求用有限的资源获取最大的收益。
现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
注意:
给定 0 和 1 的数量都不会超过 100。
给定字符串数组的长度不会超过 600。
示例 1:
输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。
示例 2:
输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2
解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ones-and-zeroes
著作权���领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
直接转载 liweiwei大佬的题解 吧，讲的很好了。
思路：把总共的 0 和 1 的个数视为背包的容量，每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成。这里的目标值是能放进背包的字符串的数量。
思路依然是“一个一个尝试，容量一点一点尝试”，每个物品分类讨论：选与不选。
第 1 步：定义状态
依然是尝试「题目问啥，就把啥定义成状态」。
dp[i][j][s] 表示输入字符串在子区间 [0, s] 能够使用 i 个 0 和 j 个 1 的字符串的最大数量。
第 2 步：状态转移方程
dp[i][j][k]= max(
// 不选择当前字符串
dp[i][j][k - 1],
// 选择了当前字符串，用减掉可用个数后并且不能选择当前字符时的最优解
dp[i - 当前字符使用 0 的个数][j - 当前字符使用 1 的个数][k - 1]
)第 3 步：输出
输出是最后一个状态，即：dp[m][n][strs.length - 1]。
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/ones-and-zeroes/solution/dong-tai-gui-hua-zhuan-huan-wei-0-1-bei-bao-wen-ti/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
/**
* @param {string[]} strs
* @param {number} m
* @param {number} n
* @return {number}
*/
let findMaxForm = function (strs, m, n) {
let sl = strs.length
if (!sl) {
return 0
}
let dp = []
for (let i = 0; i <= m; i++) {
dp[i] = []
for (let j = 0; j <= n; j++) {
dp[i][j] = []
for (let s = 0; s < sl; s++) {
let str = strs[s]
let [strM, strN] = countMAndN(str)
let pickOnlyPrev = dp[i][j][s - 1] || 0
let pickCurAndPrev = 0
if (i >= strM && j >= strN) {
pickCurAndPrev = 1 + (dp[i - strM][j - strN][s - 1] || 0)
}
dp[i][j][s] = Math.max(pickCurAndPrev, pickOnlyPrev)
}
}
}
return dp[m][n][sl - 1]
}
function countMAndN(str) {
let m = 0
let n = 0
for (let i = 0; i < str.length; i++) {
if (str[i] === "0") {
m++
} else {
n++
}
}
return [m, n]
}