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& nums) { // dp[i][j] := # of special subseqs of nums[i:] and prev + 1 = j dp.resize(nums.size(), vector(4, -1)); return countSpecialSubsequences(nums, 0, -1); } private: constexpr static int kMod = 1'000'000'007; vector> dp; int countSpecialSubsequences(const vector& 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& 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> dp(n, vector(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& 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 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]