```python
class Solution:
    def countStableSubsequences(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        
        # dp[p][c]:
        # p: 0=偶数, 1=奇数
        # c: 0=末尾连续长度为1, 1=末尾连续长度为2
        dp = [[0, 0] for _ in range(2)]
        
        for num in nums:
            p = num & 1  # 当前元素的奇偶性
            q = p ^ 1    # 相反的奇偶性
            
            # 更新长度为2: 追加到原来长度为1的同奇偶子序列后面
            # 必须先更新,使用旧值 dp[p][0]
            dp[p][1] = (dp[p][1] + dp[p][0]) % MOD
            
            # 更新长度为1:
            # 1. 自身单独作为一个新子序列 (+1)
            # 2. 追加到所有以相反奇偶性结尾的稳定子序列后面
            dp[p][0] = (dp[p][0] + dp[q][0] + dp[q][1] + 1) % MOD
        
        return (dp[0][0] + dp[0][1] + dp[1][0] + dp[1][1]) % MOD
```

核心思路:末尾状态DP

本题"稳定"定义为不能出现连续三个奇偶性相同的元素。构造子序列时,只需要关注:

· 末尾元素的奇偶性(0偶数 / 1奇数)
· 末尾连续相同奇偶性的长度(1或2)

定义 dp[p][c]:

· p:末尾奇偶性,0=偶数,1=奇数
· c:末尾连续长度,0=长度为1,1=长度为2

遍历数组,对每个元素(奇偶性 p)进行状态转移:

1. 续接同奇偶(长度1→2):
      将当前元素追加到所有以 p 结尾且长度为1的子序列后面,形成长度为2。
      dp[p][1] += dp[p][0]
      ⚠️ 关键:必须使用更新前的 dp[p][0] 旧值。
2. 开始新段(长度变为1):
      当前元素可以:
   · 单独作为新子序列:+1
   · 追加到相反奇偶性结尾的子序列后面(因为奇偶性改变,连续长度重置为1)
          dp[p][0] += dp[p^1][0] + dp[p^1][1]

更新顺序:先更新 dp[p][1],再更新 dp[p][0],确保后者不会污染前者。

最终答案为四个状态之和,对 1_000_000_007 取模。

复杂度:时间复杂度 O(n),空间复杂度 O(1),可处理 nums.length <= 10^5 的输入。

 

Logo

汇聚全球AI编程工具,助力开发者即刻编程。

更多推荐