Optimizing DI Sequence Permutations: A Python & C++ Dynamic Programming Solution 🚀🔥
Intuition 🤔The problem revolves around arranging a permutation of numbers based on D (descending) and I (ascending) constraints. Using dynamic programming, we c
# Intuition 🤔
The problem revolves around arranging a permutation of numbers based on `D` (descending) and `I` (ascending) constraints. Using dynamic programming, we can keep track of valid permutations for each step and build the solution iteratively.

# Approach 🛠️
- Use a 2D DP table, where `dp[i][j]` represents the number of ways to arrange the first `i` characters of the sequence, ending with the number `j`.
- Use prefix sums to efficiently compute cumulative sums required for `D` and `I` constraints:
1a. For `D` (descending), accumulate values for `indices k ≥ j`.
1b. For `I` (ascending), accumulate values for `indices k < j`.
- Iteratively fill the DP table, ensuring values remain within the modulo constraint 109 + 7109 + 7.
- The final result is the sum of all values in the last row of the DP table.

# Python Performance 🔥
![Screenshot from 2025-02-09 18-42-24.png](https://assets.leetcode.com/users/images/9aaa55f0-38a7-4a36-b845-c6a9ef71eb70_1739107934.7090116.png)

# C++ Performance 📈
![Screenshot from 2025-02-09 18-50-36.png](https://assets.leetcode.com/users/images/0ffce1d9-a582-43de-8f75-08120e603571_1739107972.661502.png)


# Complexity ⏳
- Time complexity:`𝑂(𝑛2)`
t1. Outer loop iterates over n, inner loop computes prefix sums and fills dp.

- Space complexity: `𝑂(𝑛2)`
s1. Space used by the DP table.

# Code 🔍
```python []
class Solution(object):
    def numPermsDISequence(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        mod = 10**9 + 7
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(1, n + 1):
            prefix = [0] * (n + 1)
            prefix[0] = dp[i-1][0]
            for j in range(1, n + 1):
                prefix[j] = (prefix[j-1] + dp[i-1][j]) % mod
            for j in range(i + 1):
                if s[i - 1] == 'D':
                    dp[i][j] = (prefix[i-1] - (prefix[j-1] if j > 0 else 0)) % mod
                else:
                    dp[i][j] = (prefix[j-1] if j > 0 else 0) % mod
        return sum(dp[n]) % mod

```
``` C++ []
class Solution {
public:
    int numPermsDISequence(string s) {
        int n = s.size();
        const int mod = 1e9 + 7;

        // Initialize DP table
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        dp[0][0] = 1;

        for (int i = 1; i <= n; ++i) {
            // Precompute prefix sums for dp[i-1]
            vector<int> prefix(n + 1, 0);
            prefix[0] = dp[i - 1][0];
            for (int j = 1; j <= n; ++j) {
                prefix[j] = (prefix[j - 1] + dp[i - 1][j]) % mod;
            }

            for (int j = 0; j <= i; ++j) {
                if (s[i - 1] == 'D') {
                    // Sum from dp[i-1][j] to dp[i-1][i-1] using prefix sum
                    dp[i][j] = (prefix[i - 1] - (j > 0 ? prefix[j - 1] : 0) + mod) % mod;
                } else {
                    // Sum from dp[i-1][0] to dp[i-1][j-1] using prefix sum
                    dp[i][j] = (j > 0 ? prefix[j - 1] : 0) % mod;
                }
            }
        }

        // Return the total sum of the last row modulo 10^9 + 7
        int result = 0;
        for (int j = 0; j <= n; ++j) {
            result = (result + dp[n][j]) % mod;
        }

        return result;
    }
};
```
['String', 'Dynamic Programming', 'Python', 'C++', 'Python3']