Leetcode Problem 1955. Count Number of Special Subsequences

1955. Count Number of Special Subsequences

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize an array dp with four elements: [1, 0, 0, 0]. The first element represents the count of empty subsequences, and the other three represent the count of subsequences ending with 0, 1, and 2 respectively.
  2. Iterate through each number in the input array nums.
  3. For each number, update the dp array as follows:
    • If the number is 0, update dp[1] by adding the current value of dp[1] and dp[0].
    • If the number is 1, update dp[2] by adding the current value of dp[2] and dp[1].
    • If the number is 2, update dp[3] by adding the current value of dp[3] and dp[2].
  4. After the loop, return the value of dp[3], which represents the count of special subsequences ending with 2.
UML Thumbnail

Recursive Memoization Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...