Efficient JS solution - DP O(N^2) (Beat 100% time)
\n\nPro tip: Xi\xE8 \uD83D\uDC9C She\'s really cute tho.\n\n# Complexity\n- Time complexity: O(n^2)\n- Space complexity: O(n)\n\n# Code\njs\nlet MOD = 100000000
![image.png](https://assets.leetcode.com/users/images/49843e4a-23a5-4dee-8579-63c97d9f77c9_1706581797.5404885.png)\n\nPro tip: Xi\xE8 \uD83D\uDC9C She\'s really cute tho.\n\n# Complexity\n- Time complexity: $$O(n^2)$$\n- Space complexity: $$O(n)$$\n\n# Code\n```js\nlet MOD = 1000000007;\nlet pre = new Uint32Array(201);\nlet cur = new Uint32Array(201);\n\n/**\n * @param {string} s\n * @return {number}\n */\nvar numPermsDISequence = function (s) {\n  let n = s.length;\n  cur.fill(0);\n  cur[0] = 1;\n\n  for (let i = 0; i < n; ++i) {\n    let tem = pre;\n    pre = cur;\n    cur = tem;\n\n    if (s[i] == "I") {\n      let sum = pre[0];\n      cur[0] = 0;\n      for (let j = 1; j <= i + 1; ++j) {\n        cur[j] = sum;\n        sum = (sum + pre[j]) % MOD;\n      }\n    } else {\n      let sum = 0;\n      cur[i + 1] = 0;\n      for (let j = i; j >= 0; --j) {\n        sum = (sum + pre[j]) % MOD;\n        cur[j] = sum;\n      }\n    }\n  }\n\n  let res = 0;\n  for (let i = 0; i <= n; ++i) res = (res + cur[i]) % MOD;\n\n  return res;\n};\n```
['Dynamic Programming', 'JavaScript']