C++ DP 100%/100%
I highly doubt if this is a real interview question or merely from contest, which adopts ideas/techniques in some fields. \n \nThe main challege to apply DP is 
I highly doubt if this is a real interview question or merely from contest, which adopts ideas/techniques in some fields. \n \nThe main challege to apply DP is the state space is too large, if remembering which numbers have been assigned. This challenge can be overcomed by using ranking. For people with background in discrete and combinatorics math, the idea is rather common. \n\nAlso, this problem requires some modeling technique commonly seen in optimal control/operations research. Dynamic programming models typically requires defining state and actions associated with the state. One can solve a DP model as a sequence of action choosing problems for each state. Another way is to regard state and action pair as a whole, and solve the DP by searching for the next state-and-actoin. As for which approach to take, it depends on specific problems. For this question, the latter one is more straightforward. \n\nTherefore, it is not a fair problem and should not be used in real interview. \n\n```\n    int numPermsDISequence(string S) {\n        const int M = 1e9 + 7, n = S.length(); \n        vector<int> curr(n + 1, 1), next(n + 1, 0);\n        for (int t = 0; t < n; ++t) {\n            char c = S[t]; \n            int sum = 0; \n            if (c == \'D\') {\n                for (int i = n - t - 1; i >=0; --i) {\n                    sum = (curr[i + 1]%M + sum%M)%M;\n                    next[i] = sum; \n                }\n            } else {\n                for (int i = 0; i < n - t; ++i) {\n                    sum = (curr[i]%M + sum%M)%M; \n                    next[i] = sum;  \n                }\n            }\n            swap(curr, next); \n        } \n        return curr.front(); \n    }\n```
[]