统计特殊子序列的数目

标签: 数组 动态规划

难度: Hard

特殊序列 是由 正整数 个 0 ，紧接着 正整数 个 1 ，最后 正整数 个 2 组成的序列。

  • 比方说，[0,1,2] 和 [0,0,1,1,1,2] 是特殊序列。
  • 相反，[2,1,0] ，[1] 和 [0,1,2,0] 就不是特殊序列。

给你一个数组 nums （仅 包含整数 0，1 和 2），请你返回 不同特殊子序列的数目 。由于答案可能很大，请你将它对 109 + 7 取余 后返回。

一个数组的 子序列 是从原数组中删除零个或者若干个元素后，剩下元素不改变顺序得到的序列。如果两个子序列的 下标集合 不同，那么这两个子序列是 不同的 。

示例 1：

输入：nums = [0,1,2,2]
输出：3
解释：特殊子序列为 [0,1,2,2]，[0,1,2,2] 和 [0,1,2,2] 。

示例 2：

输入：nums = [2,2,0,0]
输出：0
解释：数组 [2,2,0,0] 中没有特殊子序列。

示例 3：

输入：nums = [0,1,2,0,1,2]
输出：7
解释：特殊子序列包括：
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]
- [0,1,2,0,1,2]

提示：

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 2

Submission

运行时间: 154 ms

内存: 20.2 MB

class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int:
        a, b, c = 0, 0, 0
        mod = int(1e9 + 7)
        for i in nums:
            if i == 0:
                a = (2 * a + 1) % mod
            elif i == 1:
                b = (2 * b + a) % mod
            else:
                c = (2 * c + b) % mod

        return c

Explain

该题解采用动态规划的方法，通过维护三个变量a, b, c来统计以0开始，以1开始和以2结尾的特殊子序列的数量。每次遇到0时，可以选择包含或不包含当前0，因此特殊序列的数量是之前数量的两倍，再加上新开始的一个序列。遇到1时，可以选择包含或不包含当前1，因此以1开始的特殊序列数量是之前数量的两倍，加上所有可能以0结束的序列数量。同理，遇到2时，也是选择包含或不包含当前2，以2结束的序列数量是之前数量的两倍，加上所有可能以1结束的序列数量。最后返回以2结束的特殊子序列的数量。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int:
        a, b, c = 0, 0, 0  # a, b, c分别记录以0开始、以1开始、以2结束的特殊子序列数目
        mod = int(1e9 + 7)  # 模数，防止计算过程中数值过大
        for i in nums:
            if i == 0:
                a = (2 * a + 1) % mod  # 遇到0时，更新a的数量
            elif i == 1:
                b = (2 * b + a) % mod  # 遇到1时，更新b的数量
            else:
                c = (2 * c + b) % mod  # 遇到2时，更新c的数量

        return c  # 返回以2结尾的特殊子序列的数量

Explore

在给定问题中，初始化a, b, c为0确实有其特殊意义。这些变量分别表示以0开始、以1开始、以2结束的特殊子序列的数量。初始化为0意味着在序列开始之前，没有任何已形成的子序列，这是一个合理的初始化设置，因为在没有任何输入数字之前，确实不存在任何子序列。这种初始化方法为算法正确地累加新子序列提供了基础。

在遇到数字0时，将a的值更新为2*a + 1是因为每遇到一个新的0，我们可以选择将其包含在所有现有的以0开始的子序列中，这使得这些子序列的数量翻倍（即2*a）。此外，+1代表着开始一个全新的以该0为起点的子序列。因此，更新公式2*a + 1既包括了扩展现有子序列的数量，也包括了创建一个新的子序列。

当处理数字1时，加上之前累积的以0结束的子序列数量（即a的值），是因为每个以0结束的子序列都可以通过添加这个1来扩展成一个以1开始的新子序列。类似地，处理数字2时加上之前累积的以1结束的子序列数量（即b的值），是因为每个以1结束的子序列都可以通过添加这个2来扩展成一个以2结束的新子序列。这样的处理方式允许我们利用并扩展已存在的子序列结构，从而构建新的特殊子序列。

在更新变量b和c的公式中，将它们与前一个状态的变量a和b相加，是为了利用之前形成的子序列以构建更长的特殊子序列。具体来说，每个以0结束的子序列（由a表示）都可以通过添加一个1来变成一个以1开始的子序列，这就是b更新时加a的原因。同样，每个以1结束的子序列（由b表示）都可以通过添加一个2来变成以2结束的子序列，这就是c更新时加b的原因。这种依赖前一个状态的累积结果的设计是动态规划方法的核心，它允许我们从前一个状态有效地构建当前状态。