Dynamic Programming for Permutations with DI Sequence
Intuition\nThe problem involves finding the number of valid permutations based on a given string s, where \'I\' indicates that the next digit should be greater,
# Intuition\nThe problem involves finding the number of valid permutations based on a given string `s`, where \'I\' indicates that the next digit should be greater, and \'D\' indicates that the next digit should be smaller. The intuition is to use dynamic programming to build a 2D array `dp` to keep track of the number of valid permutations for each length and ending digit.\n\n## Approach\n- Initialize a 2D array `dp` of size (n + 1) x (n + 1) to represent the number of valid permutations for each length and ending digit.\n- Initialize `dp[0][0]` to 1, as there is one valid permutation of length 0 (empty sequence) ending with digit 0.\n- Iterate through each character in the given string `s` and fill in the `dp` array based on the rules:\n  - If the current character is \'I\', choose a digit greater than the previous one.\n  - If the current character is \'D\', choose a digit smaller than the previous one.\n- The result is the sum of valid permutations for the last row of `dp` (length n) modulo 10^9 + 7.\n\n## Complexity\n- Time complexity: O(n^2), where n is the length of the given string. The nested loops iterate through each position in the 2D array.\n- Space complexity: O(n^2) due to the 2D array `dp` that stores the number of valid permutations for each length and ending digit.\n\n## Code\n```python\nclass Solution(object):\n    def numPermsDISequence(self, s):\n        """\n        :type s: str\n        :rtype: int\n        """\n        MOD = 10**9 + 7\n        n = len(s)\n        \n        # dp[i][j]: Number of valid permutations of length i ending with digit j\n        dp = [[0] * (n + 1) for _ in range(n + 1)]\n        dp[0][0] = 1\n        \n        for i in range(1, n + 1):\n            for j in range(i + 1):\n                if s[i - 1] == \'I\':\n                    # If current character is \'I\', choose a digit greater than the previous one\n                    dp[i][j] = (dp[i][j] + sum(dp[i - 1][k] for k in range(j))) % MOD\n                else:\n                    # If current character is \'D\', choose a digit smaller than the previous one\n                    dp[i][j] = (dp[i][j] + sum(dp[i - 1][k] for k in range(j, i))) % MOD\n        \n        return sum(dp[n]) % MOD\n\n# Example usage:\nsol = Solution()\n\n# Example 1\ns1 = "DID"\nresult1 = sol.numPermsDISequence(s1)\nprint(result1)  # Output: 5\n\n# Example 2\ns2 = "D"\nresult2 = sol.numPermsDISequence(s2)\nprint(result2)  # Output: 1\n
['Python']