Skip to content

1955. Count Number of Special Subsequences 👍

Approach 1: Top-down

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  int countSpecialSubsequences(vector<int>& nums) {
    // dp[i][j] := # of special subseqs of nums[i:] and prev + 1 = j
    dp.resize(nums.size(), vector<int>(4, -1));
    return countSpecialSubsequences(nums, 0, -1);
  }

 private:
  static constexpr int kMod = 1'000'000'007;
  vector<vector<int>> dp;

  int countSpecialSubsequences(const vector<int>& nums, int i, int prev) {
    if (i == nums.size())
      return prev == 2;
    if (dp[i][prev + 1] != -1)
      return dp[i][prev + 1];

    long ans = 0;

    // Not include nums[i]
    ans += countSpecialSubsequences(nums, i + 1, prev);

    // Include nums[i]
    if (nums[i] == prev)
      ans += countSpecialSubsequences(nums, i + 1, prev);
    if (prev == -1 && nums[i] == 0)
      ans += countSpecialSubsequences(nums, i + 1, 0);
    if (prev == 0 && nums[i] == 1)
      ans += countSpecialSubsequences(nums, i + 1, 1);
    if (prev == 1 && nums[i] == 2)
      ans += countSpecialSubsequences(nums, i + 1, 2);

    ans %= kMod;
    return dp[i][prev + 1] = ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  public int countSpecialSubsequences(int[] nums) {
    // dp[i][j] := # of special subseqs of nums[i:] and prev + 1 = j
    dp = new int[nums.length][4];
    Arrays.stream(dp).forEach(row -> Arrays.fill(row, -1));
    return countSpecialSubsequences(nums, 0, -1);
  }

  private static final int kMod = 1_000_000_007;
  private int[][] dp;

  int countSpecialSubsequences(int[] nums, int i, int prev) {
    if (i == nums.length)
      return prev == 2 ? 1 : 0;
    if (dp[i][prev + 1] != -1)
      return dp[i][prev + 1];

    long ans = 0;

    // Not include nums[i]
    ans += countSpecialSubsequences(nums, i + 1, prev);

    // Include nums[i]
    if (nums[i] == prev)
      ans += countSpecialSubsequences(nums, i + 1, prev);
    if (prev == -1 && nums[i] == 0)
      ans += countSpecialSubsequences(nums, i + 1, 0);
    if (prev == 0 && nums[i] == 1)
      ans += countSpecialSubsequences(nums, i + 1, 1);
    if (prev == 1 && nums[i] == 2)
      ans += countSpecialSubsequences(nums, i + 1, 2);

    ans %= kMod;
    return dp[i][prev + 1] = (int) ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
  def countSpecialSubsequences(self, nums: List[int]) -> int:
    kMod = 1_000_000_007

    # dp(i, j) := # of special subseqs of nums[i:] and prev + 1 = j
    @functools.lru_cache(None)
    def dp(i: int, prev: int) -> int:
      if i == len(nums):
        return prev == 2

      ans = 0

      # Not include nums[i]
      ans += dp(i + 1, prev)

      # Include nums[i]
      if nums[i] == prev:
        ans += dp(i + 1, prev)
      if prev == -1 and nums[i] == 0:
        ans += dp(i + 1, 0)
      if prev == 0 and nums[i] == 1:
        ans += dp(i + 1, 1)
      if prev == 1 and nums[i] == 2:
        ans += dp(i + 1, 2)

      ans %= kMod
      return ans

    return dp(0, -1)

Approach 2: Bottom-up 1D DP

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  int countSpecialSubsequences(vector<int>& nums) {
    constexpr int kMod = 1'000'000'007;
    const int n = nums.size();
    // dp[i][j] := # of increasing subseqs of nums[:i] ending at j
    vector<vector<long>> dp(n, vector<long>(3));

    if (nums[0] == 0)
      dp[0][0] = 1;

    for (int i = 1; i < n; ++i) {
      for (int endingAt = 0; endingAt < 3; ++endingAt)
        dp[i][endingAt] = dp[i - 1][endingAt];

      if (nums[i] == 0)
        // Prev ending at 0 + prev ending at 0 + [0] + start new from this 0
        dp[i][0] = dp[i - 1][0] * 2 + 1;
      else if (nums[i] == 1)
        // Prev ending at 1 + prev ending at 1 + [1] + prev ending at 0 + [1]
        dp[i][1] = dp[i - 1][1] * 2 + dp[i - 1][0];
      else  // nums[i] == 2
        // Prev ending at 2 + prev ending at 2 + [2] + prev ending at 1 + [2]
        dp[i][2] = dp[i - 1][2] * 2 + dp[i - 1][1];

      for (int endingAt = 0; endingAt < 3; ++endingAt)
        dp[i][endingAt] %= kMod;
    }

    return dp.back()[2];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int countSpecialSubsequences(int[] nums) {
    final int kMod = 1_000_000_007;
    final int n = nums.length;
    // dp[i][j] := # of increasing subseqs of nums[:i] ending at j
    long[][] dp = new long[n][3];

    if (nums[0] == 0)
      dp[0][0] = 1;

    for (int i = 1; i < n; ++i) {
      for (int endingAt = 0; endingAt < 3; ++endingAt)
        dp[i][endingAt] = dp[i - 1][endingAt];

      if (nums[i] == 0)
        // Prev ending at 0 + prev ending at 0 + [0] + start new from this 0
        dp[i][0] = dp[i - 1][0] * 2 + 1;
      else if (nums[i] == 1)
        // Prev ending at 1 + prev ending at 1 + [1] + prev ending at 0 + [1]
        dp[i][1] = dp[i - 1][1] * 2 + dp[i - 1][0];
      else // nums[i] == 2
        // Prev ending at 2 + prev ending at 2 + [2] + prev ending at 1 + [2]
        dp[i][2] = dp[i - 1][2] * 2 + dp[i - 1][1];

      for (int endingAt = 0; endingAt < 3; ++endingAt)
        dp[i][endingAt] %= kMod;
    }

    return (int) dp[n - 1][2];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
  def countSpecialSubsequences(self, nums: List[int]) -> int:
    kMod = 1_000_000_007
    n = len(nums)
    # dp[i][j] := # of increasing subseqs of nums[:i] ending at j
    dp = [[0] * 3 for _ in range(n)]

    if nums[0] == 0:
      dp[0][0] = 1

    for i in range(1, n):
      for endingAt in range(3):
        dp[i][endingAt] = dp[i - 1][endingAt]

      if nums[i] == 0:
        # Prev ending at 0 + prev ending at 0 + [0] + start new from this 0
        dp[i][0] = dp[i - 1][0] * 2 + 1
      elif nums[i] == 1:
        # Prev ending at 1 + prev ending at 1 + [1] + prev ending at 0 + [1]
        dp[i][1] = dp[i - 1][1] * 2 + dp[i - 1][0]
      else:  # nums[i] == 2
        # Prev ending at 2 + prev ending at 2 + [2] + prev ending at 1 + [2]
        dp[i][2] = dp[i - 1][2] * 2 + dp[i - 1][1]

      for endingAt in range(3):
        dp[i][endingAt] %= kMod

    return dp[-1][2]

Approach 3: Bottom-up $O(1)$ DP

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int countSpecialSubsequences(vector<int>& nums) {
    constexpr int kMod = 1'000'000'007;
    const int n = nums.size();
    // dp[j] := # of increasing subseqs of nums so far ending at j
    vector<long> dp(3);

    if (nums[0] == 0)
      dp[0] = 1;

    for (int i = 1; i < n; ++i) {
      if (nums[i] == 0)
        dp[0] = dp[0] * 2 + 1;
      else if (nums[i] == 1)
        dp[1] = dp[1] * 2 + dp[0];
      else  // nums[i] == 2
        dp[2] = dp[2] * 2 + dp[1];

      for (int endingAt = 0; endingAt < 3; ++endingAt)
        dp[endingAt] %= kMod;
    }

    return dp[2];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int countSpecialSubsequences(int[] nums) {
    final int kMod = 1_000_000_007;
    final int n = nums.length;
    // dp[j] := # of increasing subseqs of nums so far ending at j
    long[] dp = new long[3];

    if (nums[0] == 0)
      dp[0] = 1;

    for (int i = 1; i < n; ++i) {
      if (nums[i] == 0)
        dp[0] = dp[0] * 2 + 1;
      else if (nums[i] == 1)
        dp[1] = dp[1] * 2 + dp[0];
      else // nums[i] == 2
        dp[2] = dp[2] * 2 + dp[1];

      for (int endingAt = 0; endingAt < 3; ++endingAt)
        dp[endingAt] %= kMod;
    }

    return (int) dp[2];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def countSpecialSubsequences(self, nums: List[int]) -> int:
    kMod = 1_000_000_007
    n = len(nums)
    # dp[j] := # of increasing subseqs of nums so far ending at j
    dp = [0] * 3

    if nums[0] == 0:
      dp[0] = 1

    for i in range(1, n):
      if nums[i] == 0:
        dp[0] = dp[0] * 2 + 1
      elif nums[i] == 1:
        dp[1] = dp[1] * 2 + dp[0]
      else:  # nums[i] == 2
        dp[2] = dp[2] * 2 + dp[1]

      for endingAt in range(3):
        dp[endingAt] %= kMod

    return dp[2]