【每日一题】- 2019-08-20 - 474. 一和零 about leetcode HOT 4 CLOSED

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 * F(i,C) = max(F(i-1,C),F(i-1,C-w)+v); 0,1背包公式
 * 
 * 多维版
 * F(i,m,n) = max(F(i-1,m,n),F(i-1,m-j,n-k)+1); j=当前字符串的0数量，k为1的数量
 * 
 * 每遍历到strs的一个位置时，有两种选择，选择当前字符串，或者不选择
 * 如果选择，那么当前F(i,m,n)的最优结果等于减去这个字符串占用的01数量后的最优结果，即F(i-1,m-j,n-k)+1
 * 如果不选择，那么当前F(i,m,n)的最优结果等于遍历到上一个字符串时的结果，即F(i-1,m,n)
 * 
 */
var findMaxForm = function (strs, m, n) {
    if (strs.length == 0) return 0;
    var dp = Array.from({
        length: m + 1
    }, () => new Array(n + 1).fill(0));
    for (var i = 0; i < strs.length; i++) {
        var count1 = 0,
            count0 = 0;
        for (var item of strs[i]) {
            if (item == '1') count1++;
            else count0++;
        }

        for (var k = m; k >= count0; k--) {
            for (var j = n; j >= count1; j--) {
                dp[k][j] = Math.max(dp[k][j], dp[k - count0][j - count1] + 1);
            }
        }
    }

    return dp[m][n];
};