Skip to content
The Chat Archive
claude-3-7-sonnet-20250219-thinking-32k· Anthropic LMArena Human Preference 140K

下面代码逻辑正确,用前缀和优化计算过程。 class Solution { public int numberOfStableArrays(int zero, int one,…

  1. User

    下面代码逻辑正确,用前缀和优化计算过程。 class Solution { public int numberOfStableArrays(int zero, int one, int limit) { final long MOD = (long)1e9 + 7; int n = zero + one;

        // dp[i][j] 表示剩余 i 个零和 j 个一时的方案数
        long[][][] dp = new long[zero + 1][one + 1][2];
    
        // 初始化:当只剩一种数字时,检查是否超过 limit
        for (int z = 0; z <= zero; z++) {
            dp[z][0][0] = z <= limit ? 1 : 0;
        }
        for (int o = 0; o <= one; o++) {
            dp[0][o][1] = o <= limit ? 1 : 0;
        }
    
        // 动态规划填充 dp 表
        for (int z = 1; z <= zero; z++) {
            for (int o = 1; o <= one; o++) {
                // 当前以零开头的情况
                for (int len = 1; len <= Math.min(limit, z); len++) {
                    if (z - len >= 0) {
                        dp[z][o][0] = (dp[z][o][0] + dp[z - len][o][1]) % MOD;
                    }
                }
                // 当前以一开头的情况
                for (int len = 1; len <= Math.min(limit, o); len++) {
                    if (o - len >= 0) {
                        dp[z][o][1] = (dp[z][o][1] + dp[z][o - len][0]) % MOD;
                    }
                }
            }
        }
    
        return (int) ((dp[zero][one][0] + dp[zero][one][1]) % MOD);
    }
    

    }

  2. Assistant

    下面是使用前缀和优化的代码实现:

    class Solution {
        public int numberOfStableArrays(int zero, int one, int limit) {
            final long MOD = (long)1e9 + 7;
    
            // dp[i][j][k] 表示剩余 i 个零和 j 个一,结尾是k(0或1)的方案数
            long[][][] dp = new long[zero + 1][one + 1][2];
            
            // 前缀和数组,用于优化内部循环
            long[][][] prefixSum = new long[zero + 1][one + 1][2];
    
            // 初始化:当只剩一种数字时的情况
            for (int z = 0; z <= zero; z++) {
                dp[z][0][0] = z <= limit ? 1 : 0;
                prefixSum[z][0][0] = dp[z][0][0];
            }
            for (int o = 0; o <= one; o++) {
                dp[0][o][1] = o <= limit ? 1 : 0;
                prefixSum[0][o][1] = dp[0][o][1];
            }
    
            // 动态规划填充 dp 表
            for (int z = 1; z <= zero; z++) {
                for (int o = 1; o <= one; o++) {
                    // 计算以0结尾的方案数
                    int minZ = Math.max(0, z - limit);
                    dp[z][o][0] = (prefixSum[z-1][o][1] - (minZ > 0 ? prefixSum[minZ-1][o][1] : 0) + MOD) % MOD;
                    
                    // 计算以1结尾的方案数
                    int minO = Math.max(0, o - limit);
                    dp[z][o][1] = (prefixSum[z][o-1][0] - (minO > 0 ? prefixSum[z][minO-1][0] : 0) + MOD) % MOD;
                    
                    // 更新前缀和
                    prefixSum[z][o][0] = (prefixSum[z-1][o][0] + dp[z][o][0]) % MOD;
                    prefixSum[z][o][1] = (prefixSum[z][o-1][1] + dp[z][o][1]) % MOD;
                }
            }
    
            return (int)((dp[zero][one][0] + dp[zero][one][1]) % MOD);
        }
    }
    

    优化说明:

    1. 前缀和数组:

      • 新增了 prefixSum[z][o][k] 数组,表示所有 dp[0...z][0...o][k] 的累加和
      • 对于 prefixSum[z][o][0] 维护的是所有 dp[0...z][o][0] 的和
      • 对于 prefixSum[z][o][1] 维护的是所有 dp[z][0...o][1] 的和
    2. 优化内部循环:

      • 原代码中有两个 O(limit) 的内部循环,现在用前缀和一次性计算
      • 对于以0结尾的方案数,通过 prefixSum[z-1][o][1] - prefixSum[minZ-1][o][1] 计算
      • 对于以1结尾的方案数,通过 prefixSum[z][o-1][0] - prefixSum[z][minO-1][0] 计算
    3. 处理边界条件:

      • 当 minZ 或 minO 为0时,需要特别处理前缀和差值计算
      • 为避免负数导致的模运算问题,加上 MOD 再取模
    4. 时间复杂度:

      • 从 O(zero * one * limit) 优化到 O(zero * one)
      • 对于输入范围 [1,1000],性能提升显著

    通过前缀和优化,去除了内部的 O(limit) 循环,使算法在 zero 和 one 较大时能更高效地运行。

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.