[C++/Java/Python] DP Solution O(N^2)
Intuition\ndp[i][j] means the number of possible permutations of first i + 1 digits,\nwhere the i + 1th digit is j + 1th smallest in the rest of unused digits.\
# Intuition\n`dp[i][j]` means the number of possible permutations of first `i + 1` digits,\nwhere the `i + 1`th digit is `j + 1`th smallest in the rest of unused digits.\n\n\nOk, may not make sense ... Let\'s see the following diagram.\n![image](https://s3-lc-upload.s3.amazonaws.com/users/lee215/image_1536486527.png)\n\nI take the example of `S = "DID"`.\nIn the parenthesis, I list all possible permutations.\n\nThe permutation can start from `1, 2, 3, 4`.\nSo `dp[0][0] = dp[0][1] = dp[0][2] = dp[0][3] = 1`.\n\nWe decrese from the first digit to the second,\nthe down arrow show the all possibile decresing pathes.\n\nThe same, because we increase from the second digit to the third,\nthe up arrow show the all possibile increasing pathes.\n\n`dp[2][1] = 5`, mean the number of permutations\nwhere the third digitis the second smallest of the rest.\nWe have 413,314,214,423,324.\nFow example 413, where 2,3 are left and 3 the second smallest of them.\n<br>\n\n# Explanation\nAs shown in the diagram,\nfor "I", we calculate prefix sum of the array,\nfor "D", we calculate sufixsum of the array.\n<br>\n\n# Complexity\nTime `O(N^2)`\nSpace `O(N^2)`\n<br>\n\n**C++:**\n```cpp\n    int numPermsDISequence(string S) {\n        int n = S.length(), mod = 1e9 + 7;\n        vector<vector<int>> dp(n + 1, vector<int>(n + 1));\n        for (int j = 0; j <= n; j++) dp[0][j] = 1;\n        for (int i = 0; i < n; i++)\n            if (S[i] == \'I\')\n                for (int j = 0, cur = 0; j < n - i; j++)\n                    dp[i + 1][j] = cur = (cur + dp[i][j]) % mod;\n            else\n                for (int j = n - i - 1, cur = 0; j >= 0; j--)\n                    dp[i + 1][j] = cur = (cur + dp[i][j + 1]) % mod;\n        return dp[n][0];\n    }\n```\n\n**Java:**\n```java\n    public int numPermsDISequence(String S) {\n        int n = S.length(), mod = (int)1e9 + 7;\n        int[][] dp = new int[n + 1][n + 1];\n        for (int j = 0; j <= n; j++) dp[0][j] = 1;\n        for (int i = 0; i < n; i++)\n            if (S.charAt(i) == \'I\')\n                for (int j = 0, cur = 0; j < n - i; j++)\n                    dp[i + 1][j] = cur = (cur + dp[i][j]) % mod;\n            else\n                for (int j = n - i - 1, cur = 0; j >= 0; j--)\n                    dp[i + 1][j] = cur = (cur + dp[i][j + 1]) % mod;\n        return dp[n][0];\n    }\n```\n\n# Solution 2:\nNow as we did for every DP, make it 1D dp.\nTime `O(N^2)`\nSpace `O(N)`\n\n**C++:**\n```cpp\n    int numPermsDISequence(string S) {\n        int n = S.length(), mod = 1e9 + 7;\n        vector<int> dp(n + 1, 1), dp2(n);\n        for (int i = 0; i < n; dp = dp2, i++) {\n            if (S[i] == \'I\')\n                for (int j = 0, cur = 0; j < n - i; j++)\n                    dp2[j] = cur = (cur + dp[j]) % mod;\n            else\n                for (int j = n - i - 1, cur = 0; j >= 0; j--)\n                    dp2[j] = cur = (cur + dp[j + 1]) % mod;\n        }\n        return dp[0];\n    }\n```\n\n**Java:**\n```java\n    public int numPermsDISequence(String S) {\n        int n = S.length(), mod = (int)1e9 + 7;\n        int[] dp = new int[n + 1], dp2 = new int[n];;\n        for (int j = 0; j <= n; j++) dp[j] = 1;\n        for (int i = 0; i < n; i++) {\n            if (S.charAt(i) == \'I\')\n                for (int j = 0, cur = 0; j < n - i; j++)\n                    dp2[j] = cur = (cur + dp[j]) % mod;\n            else\n                for (int j = n - i - 1, cur = 0; j >= 0; j--)\n                    dp2[j] = cur = (cur + dp[j + 1]) % mod;\n            dp = Arrays.copyOf(dp2, n);\n        }\n        return dp[0];\n    }\n```\n\n**Python2**\n```py\n    def numPermsDISequence(self, S):\n        dp = [1] * (len(S) + 1)\n        for c in S:\n            if c == "I":\n                dp = dp[:-1]\n                for i in range(1, len(dp)):\n                    dp[i] += dp[i - 1]\n            else:\n                dp = dp[1:]\n                for i in range(len(dp) - 1)[::-1]:\n                    dp[i] += dp[i + 1]\n        return dp[0] % (10**9 + 7)\n```\n**Python3**\n```py\n    def numPermsDISequence(self, S):\n        dp = [1] * (len(S) + 1)\n        for a, b in zip(\'I\' + S, S):\n            dp = list(itertools.accumulate(dp[:-1] if a == b else dp[-1:0:-1]))\n        return dp[0] % (10**9 + 7)\n```
[]