Formatted question description: https://leetcode.ca/all/1955.html

# 1955. Count Number of Special Subsequences

## Level

Hard

## Description

A sequence is **special** if it consists of a **positive** number of `0`

s, followed by a **positive** number of `1`

s, then a **positive** number of `2`

s.

- For example,
`[0,1,2]`

and`[0,0,1,1,1,2]`

are special. - In contrast,
`[2,1,0]`

,`[1]`

, and`[0,1,2,0]`

are not special.

Given an array `nums`

(consisting of **only** integers `0`

, `1`

, and `2`

), return *the number of different subsequences that are special*. Since the answer may be very large,

**return it modulo**

`10^9 + 7`

.A **subsequence** of an array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. Two subsequences are **different** if the **set of indices** chosen are different.

**Example 1:**

**Input:** nums = [0,1,2,2]

**Output: **3

**Explanation:** The special subsequences are [0,1,2,2], [0,1,2,2], and [0,1,2,2].

**Example 2:**

**Input:** nums = [2,2,0,0]

**Output:** 0

**Explanation:** There are no special subsequences in [2,2,0,0].

**Example 3:**

**Input:** nums = [0,1,2,0,1,2]

**Output:** 7

**Explanation:** The special subsequences are:

- [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]

**Constraints:**

`1 <= nums.length <= 10^5`

`0 <= nums[i] <= 2`

## Solution

Use dynamic programming. Use `dp[i][j]`

to represent the number of special subsequences up to index `i`

that end with number `j`

. Note that the special subsequences do not necessary end with 2, but satisfy that all 0s come before 1s and all 1s come before 2s.

When `i = 0`

, `dp[0][0] = 1`

if and only if `nums[0] = 0`

. For `i`

from 1 to `nums.length - 1`

, `dp[i][0]`

is calculated as `dp[i - 1][0] * 2 + 1`

if `nums[i] = 0`

, and `dp[i - 1][0]`

otherwise. For `dp[i][j]`

where `j`

is 1 or 2, if `nums[i] = j`

, then `dp[i][j] = dp[i - 1][j] * 2 + dp[i - 1][j - 1]`

, otherwise `dp[i][j] = dp[i - 1][j]`

. Finally, return `dp[nums.length - 1][2]`

.

```
class Solution {
public int countSpecialSubsequences(int[] nums) {
final int MODULO = 1000000007;
int length = nums.length;
int[][] dp = new int[length][3];
if (nums[0] == 0)
dp[0][0] = 1;
for (int i = 1; i < length; i++) {
int num = nums[i];
if (num == 0)
dp[i][0] = (dp[i - 1][0] * 2 + 1) % MODULO;
else
dp[i][0] = dp[i - 1][0];
if (num == 1) {
dp[i][1] = dp[i - 1][1] * 2 % MODULO;
dp[i][1] = (dp[i][1] + dp[i - 1][0]) % MODULO;
} else
dp[i][1] = dp[i - 1][1];
if (num == 2) {
dp[i][2] = dp[i - 1][2] * 2 % MODULO;
dp[i][2] = (dp[i][2] + dp[i - 1][1]) % MODULO;
} else
dp[i][2] = dp[i - 1][2];
}
return dp[length - 1][2];
}
}
```