1955-count-number-of-special-subsequences.js

/*
 * @lc app=leetcode id=1955 lang=javascript
 *
 * [1955] Count Number of Special Subsequences
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
const countSpecialSubsequences = function (nums) {
  const dp = Array(3).fill(0),
    mod = 10 ** 9 + 7
  for (let e of nums) {
    dp[e] = (((dp[e] + dp[e]) % mod) + (e > 0 ? dp[e - 1] : 1)) % mod
  }
  return dp[2]
}

// another

/**
 * @param {number[]} nums
 * @return {number}
 */
const countSpecialSubsequences = function(nums) {
  const mod = 10 ** 9 + 7
  const dp = Array.from({length: 10 **5 + 1}, () => Array(4).fill(-1))
  let n = nums.length, a = nums
  return f(0, 0)
  function f(index, firstMandatory) {
      if (index == n && firstMandatory == 3) {
          return 1;
      }
      if (index == n) {
          return 0;
      }
      if (dp[index][firstMandatory] >= 0) {
          return dp[index][firstMandatory];
      }
      let result = 0;
      if (a[index] == firstMandatory) {
          result = (result +
                  f(index + 1, firstMandatory) +
                  f(index + 1, firstMandatory + 1)
          ) % mod;
      }
      result = (result + f(index + 1, firstMandatory)) % mod;

      return dp[index][firstMandatory] = result;
  }
};