In depth explanation of relative ranking approach (Base case + State transition + Answer) .
IntuitionFirstly, let's define the dp state and then understand its meaning in depth .
dp[i][j] here represents the number of ways to constuct the permutation u
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Firstly, let's define the $$dp$$ state and then understand its meaning in depth .
$$dp[i][j]\ $$here represents the number of ways to constuct the permutation using numbers from $$0$$ to $$i$$ and the $$(i+1)^{th}$$ number of this permutation has the $$(j+1)^{th}$$ rank .

*Note that the $$(i+1)^{th}$$ number is not equal to $$(j+1)$$ but it is having $$(j+1)^{th}$$ rank in the current permutation. For example, in the permutation $$[ 2\ 4\  3\  0\ 1 ]$$, the rank of $$2$$ is $$1$$, the rank of $$4$$ is $$2$$, the rank of $$3$$ is also $$2$$, the rank of $$0$$ is $$1$$ and the rank of $$1$$ is also $$1$$.* 

This means that there are $$j$$ elements smaller than the current element that have already occurred in the permutation before index $$i$$ .


# Approach
<!-- Describe your approach to solving the problem. -->
Now, let's understand the state transitions :
 * When $$s_i = \ 'D'$$ then the previous index must be greater than the current index . Since the current element has a rank of $$(j+1)$$, therefore the previous element must have a rank equal to either $$(j+1)\ or\ (j+2)\ or ... or\ i$$ . 
```
dp[i][j] = dp[i-1][j] + dp[i-1][j+1] + ... + dp[i-1][i-1]
```
 * When $$s_i = \ 'I'$$ then the previous index must be lesser than the current index . Since the current element has a rank of $$(j+1)$$, therefore the previous element must have a rank equal to either $$1\ or\ 2\ or ... or\ (j-1)\ or\ j$$ . 
```
dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j-1]
```

Now, let's see the base case :
When $$i=0$$ and $$j=0$$ then there can be only $$1$$ permutation possible which is equal to $$[ 0 ]$$ . Therefore, $$dp[0][0] = 1$$ .

Now, let's understand the way to obtain final answer.
The $$(n+1)^{th}$$ element of the permutation can have a rank of either $$1\ or\ 2\ or\ 3\ or\ ...\ or\ (n+1)$$ .
```
ans = dp[n][0] + dp[n][1] + dp[n][2] + ... + dp[n][n] .
```
# Complexity
- Time complexity: $$O(n^3)$$ .
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(n^2)$$ .
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int numPermsDISequence(string s) {
        int n=(int)s.length(), mod=1e9+7;
        vector<vector<int>> dp(n+1, vector<int> (n+1, -1));
        for (int i=0; i<=n; i++) {
            for (int j=0; j<=i; j++) {
                if (i == 0) {
                    dp[i][j] = 1;
                    continue;
                }
                int total=0;
                if (s.at(i-1) == 'D') {
                    for (int p=j; p<i; p++) {
                        int val = dp[i-1][p];
                        total = (total%mod + val%mod)%mod;
                    }
                } else {
                    for (int p=0; p<j; p++) {
                        int val = dp[i-1][p];
                        total = (total%mod + val%mod)%mod;
                    }
                }
                dp[i][j] = total;
            }
        }
        int ans=0;
        for (int i=0; i<=n; i++) {
            int val = dp[n][i];
            ans = (ans%mod + val%mod)%mod;
        }
        return ans;
    }
};
```
['C++']