Problem statement

https://leetcode.com/problems/count-number-of-special-subsequences/

Solution

Let dp[i] means number of longest increasing subsequences which end with i - 1, that is

  1. dp[1] is for ending with 0.
  2. dp[2] is for ending with 1.
  3. dp[3] is for ending with 2.

Then if new symbol is:

  1. 0, then we have dp[1] = 2*dp[1] + 1, because we extend all sequences of 0 here.
  2. 1, then we have dp[2] = 2*dp[2] + dp[1], because we can extend all sequences of ends with 0 and 1.
  3. 2, then we have dp[3] = 2*dp[3] + dp[2], because we can extend all sequences of ends with 1 and 2. Notice, that we can not extend ending with 0, because we need to have j >= 1 ones.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def countSpecialSubsequences(self, nums):
        dp = [1, 0, 0, 0]
        for i in nums:
            dp[i+1] = (2*dp[i+1] + dp[i]) % (10**9 + 7)
            
        return dp[-1]