DeepSeek LeetCode 3686. 稳定子序列的数量 Java实现

```java
class Solution {
private static final int MOD = 1_000_000_007;

public int countStableSubsequences(int[] nums) {
// dp[p][c]:
// p = 0 表示偶数，1 表示奇数
// c = 0 表示结尾连续同奇偶长度为1，c = 1 表示长度为2
long[][] dp = new long[2][2];

for (int num : nums) {
int x = num & 1; // 当前元素的奇偶性
int y = x ^ 1; // 相反的奇偶性

// 关键：先更新 dp[x][1]，使用旧值 dp[x][0]，避免被本轮更新污染
// 把原来以 x 结尾且长度为 1 的子序列，追加当前元素，变成以 x 结尾长度为 2
dp[x][1] = (dp[x][1] + dp[x][0]) % MOD;

// 更新 dp[x][0]：
// 1. 保留原来的（不选当前元素）
// 2. 追加到以相反奇偶性结尾的子序列后面，此时长度为1
// 3. 当前元素单独作为一个新子序列
dp[x][0] = (dp[x][0] + dp[y][0] + dp[y][1] + 1) % MOD;
}

long ans = (dp[0][0] + dp[0][1] + dp[1][0] + dp[1][1]) % MOD;
return (int) ans;
}
}
```

核心思路：结尾状态DP

这道题“稳定”的定义是子序列中不能出现连续三个奇偶性相同的元素。因此，我们构造子序列时，只需要关心它末尾元素的奇偶性，以及末尾连续相同奇偶性的长度是1还是2。

我们定义dp[p][c]：

· p = 0代表偶数，1代表奇数。
· c = 0代表以奇偶性p结尾，且连续长度恰好为1；c = 1代表连续长度恰好为2。

遍历数组，对每个元素x（奇偶性为p），进行状态更新：

1. 续接同奇偶：将当前元素加到所有以p结尾且长度为1的子序列后面，使其变为长度2。即dp[p][1] += dp[p][0]（关键：这里必须用更新前的dp[p][0]值）。
2. 开始新段：当前元素可以：
· 单独作为一个新子序列，长度1（+1）。
· 加到所有以相反奇偶性p^1结尾的稳定子序列后面，因为奇偶性改变，新的连续长度变为1。即dp[p][0] += dp[p^1][0] + dp[p^1][1]。

注意更新顺序：必须先更新dp[p][1]再更新dp[p][0]，确保dp[p][0]使用的是旧值，不会把本轮刚生成的“长度为1”的子序列（来自dp[p][0]旧值）错误地也计入长度2的统计。

最终答案就是四个状态之和，并对1_000_000_007取模。

该算法时间复杂度O(n)，空间复杂度O(1)，可高效处理nums.length <= 10^5的数据规模。