claude-3-7-sonnet-20250219-thinking-32k· Anthropic LMArena Human Preference 140K
下面代码逻辑正确,用前缀和优化计算过程。 class Solution { public int numberOfStableArrays(int zero, int one,…
- 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); }}
- 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); } }优化说明:
-
前缀和数组:
- 新增了
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]的和
- 新增了
-
优化内部循环:
- 原代码中有两个 O(limit) 的内部循环,现在用前缀和一次性计算
- 对于以0结尾的方案数,通过
prefixSum[z-1][o][1] - prefixSum[minZ-1][o][1]计算 - 对于以1结尾的方案数,通过
prefixSum[z][o-1][0] - prefixSum[z][minO-1][0]计算
-
处理边界条件:
- 当
minZ或minO为0时,需要特别处理前缀和差值计算 - 为避免负数导致的模运算问题,加上 MOD 再取模
- 当
-
时间复杂度:
- 从 O(zero * one * limit) 优化到 O(zero * one)
- 对于输入范围 [1,1000],性能提升显著
通过前缀和优化,去除了内部的 O(limit) 循环,使算法在 zero 和 one 较大时能更高效地运行。
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.