pythonclass Solution:def countStableSubsequences(self, nums: List[int]) - int:MOD 10**9 7# dp[p][c]:# p: 0偶数, 1奇数# c: 0末尾连续长度为1, 1末尾连续长度为2dp [[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) % MODreturn (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长度为11长度为2遍历数组对每个元素奇偶性 p进行状态转移1. 续接同奇偶长度1→2将当前元素追加到所有以 p 结尾且长度为1的子序列后面形成长度为2。dp[p][1] dp[p][0]⚠️ 关键必须使用更新前的 dp[p][0] 旧值。2. 开始新段长度变为1当前元素可以· 单独作为新子序列1· 追加到相反奇偶性结尾的子序列后面因为奇偶性改变连续长度重置为1dp[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 的输入。
