C solution beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem is asking us to find the number of permutations of a string of length n tha
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem is asking us to find the number of permutations of a string of length n that satisfy the condition that the string only contains \'I\' and \'D\' and where \'I\' represents increasing and \'D\' represents decreasing.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can use Dynamic Programming to solve this problem. We create a 2D array dp[n+1][n+1] where dp[i][j] represent the number of permutations of the first i characters that end with j \'I\'s.\n\nWe iterate through the string one character at a time, and for each character, we check if it is an \'I\' or a \'D\'. If it is an \'I\', we update dp[i][j] using dp[i-1][k] where k is from j to i-1. If it is a \'D\', we update dp[i][j] using dp[i-1][k] where k is from 0 to j-1.\n\n\n# Complexity\n- Time complexity: O(n^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nint numPermsDISequence(char * s){\n    int n = strlen(s), mod = 1e9 + 7;\n    int dp[n + 1][n + 1];\n    memset(dp, 0, sizeof(dp));\n    dp[0][0] = 1;\n    for (int i = 1; i <= n; i++)\n    {\n        for (int j = 0; j <= i; j++)\n        {\n            if (s[i - 1] == \'D\')\n                for (int k = j; k < i; k++)\n                    dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;\n            else\n                for (int k = 0; k < j; k++)\n                    dp[i][j] = (dp[i][j] + dp[i - 1][k]) % mod;\n        }\n    }\n    int ans = 0;\n    for (int i = 0; i <= n; i++)\n        ans = (ans + dp[n][i]) % mod;\n    return ans;\n}\n```
['C']