LeetCode Ones and Zeros问题：3D数组解法无法通过样例求助

问题情况 #

我在解决LeetCode的「1和0」问题时，参考DP维度优化与填表顺序的思路实现了基于3D数组的动态规划解法，但无法通过样例测试。以下是我的代码、样例输入输出，请求排查问题：

我的代码 #

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function(strs, m, n) {
    const len = strs.length;
    const dp = new Array(len+1).fill(0).map((_, i) => {
        return new Array(m+1).fill(0).map((_, j) => {
            return new Array(n+1).fill(0);
        });
    });

    const get1s = (ele) => {
        const arr = ele.split('');
        const ones = arr.reduce((acc, a) => acc + parseInt(a));
        return ones;
    }

    const get0s = (ele) => {
        const ones = get1s(ele);
        const zeros = ele.length - ones;
        return zeros;
    }

    for(let i=1; i<=len; ++i) {
        const ele = strs[i-1];
        const zeros = get0s(ele);
        const ones = get1s(ele);

        for(let j=0; j<=m; ++j) {
            for(let k=0; k<=n; ++k) {
                if(j-zeros >=0 && k-ones >= 0) {
                    dp[i][j][k] = 1 + dp[i-1][j-zeros][k-ones];
                } else {
                    dp[i][j][k] = dp[i-1][j][k];
                }
            }
        }
    }

    return dp[len][m][n];        
};

样例输入输出 #

• 输入数组：["10","0001","111001","1","0"]
• m = 5，n = 3
• 预期输出：4

问题排查与修复 #

你的代码核心问题在于动态规划的状态转移逻辑错误：当当前字符串可以被选取（j-zeros >=0 && k-ones >=0）时，你直接赋值为1 + dp[i-1][j-zeros][k-ones]，但忽略了「不选取当前字符串」的情况可能得到更大的值。正确的转移应该是在「选」和「不选」中取最大值。

同时补充一个细节：get1s函数里的reduce需要添加初始值0，避免空字符串场景下返回undefined，让代码更健壮。

完整修复后的代码 #

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function(strs, m, n) {
    const len = strs.length;
    const dp = new Array(len+1).fill(0).map((_, i) => {
        return new Array(m+1).fill(0).map((_, j) => {
            return new Array(n+1).fill(0);
        });
    });

    const get1s = (ele) => {
        const arr = ele.split('');
        const ones = arr.reduce((acc, a) => acc + parseInt(a), 0);
        return ones;
    }

    const get0s = (ele) => {
        const ones = get1s(ele);
        const zeros = ele.length - ones;
        return zeros;
    }

    for(let i=1; i<=len; ++i) {
        const ele = strs[i-1];
        const zeros = get0s(ele);
        const ones = get1s(ele);

        for(let j=0; j<=m; ++j) {
            for(let k=0; k<=n; ++k) {
                if(j-zeros >=0 && k-ones >= 0) {
                    dp[i][j][k] = Math.max(dp[i-1][j][k], 1 + dp[i-1][j-zeros][k-ones]);
                } else {
                    dp[i][j][k] = dp[i-1][j][k];
                }
            }
        }
    }

    return dp[len][m][n];        
};

内容的提问来源于stack exchange，提问作者kenpeter