Share my O(N^3) => O(N^2) C++ DP solution. Including the thoughts of improvement.
Came up with the original idea during contest, so might not be the best. But it works.\nc++\nclass Solution {\npublic:\n    int numPermsDISequence(string S) {\n
Came up with the original idea during contest, so might not be the best. But it works.\n```c++\nclass Solution {\npublic:\n    int numPermsDISequence(string S) {\n        int N = S.length() + 1;\n        int MOD = 1e9 + 7;\n        // dp[i][j] number of permutation whose length is i and end with j\n        int dp[202][202] = {};\n        dp[1][1] = 1;\n        for (int i = 2; i <= N; ++i) {\n            // length is i\n            for (int j = 1; j <= i; ++j) {\n                // end with j\n                if (S[i - 2] == \'D\') {\n                    // decrease to j\n                    // add all string with length i - 1 and last digit is greater than or equal to j\n                    for (int k = j; k <= i; ++k) {\n                        dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD;\n                    }\n                } else {\n                    // increase to j\n                    // add all string with length i - 1 and last digit is smaller than j\n                    for (int k = 1; k < j; ++k) {\n                        dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD;\n                    }\n                }\n            }\n        }\n        int ans = 0;\n        for (int i = 1; i <= N; ++i) ans = (ans + dp[N][i]) % MOD;\n        return ans;\n    }\n};\n```\n\n**UPDATE 9/9/2018**:\nThanks to `@chosun1`, I used prefix sum to save the result which reduce the complexity to O(N ^ 2). There is no need to keep a separate 2d array for prefix sum, just change the definition of dp array is fine. Here is the updated code, it is even shorter.\n\n`dp[i][j]` means number of permutation whose length is `i` and end with **at most** `j`.\n\nLet\'s say the current position of DI sequence is `\'D\'`, \nSo, `dp[i][j] = dp[i][j-1] + X`, where `X` is number of permutations whose length is `i` and end exactly with `j`. We can calculate it by adding number of permutations whose length is `i-1` and end with `{j, j+1, ..., i-1}`, because they will satisfy the condition of "decreasing to j". (*Wait! Wait! Why start with j not j + 1?, see the bolded explaination below.*)\nAccording to the definition of dp array, we can get `X = dp[i-1][i-1] - dp[i-1][j-1]`.\n\nIf the DI sequence is `\'I\'`, it\'s similiar.\n\n**So, why start with j, not j + 1, since the sequence is decreasing to j?**\n`Thought Experiment`: In the sequence with length of `i-1`, the largest number in this sequence should be `i-1`. However, when we are dealing with length `i` and end with `j`, the previous sequence has already another `j` and we should also add `i` to the sequence. What we can do is, **add one to all those numbers greater than or equal to j**. This operation will make the largest number to be `i` without breaking the sequence property, also, it will free the `j` so that we can use it at the end of the sequence. By this thought experiment, we can easily get the result of `X`. For example, if the sequence is `{3,4,1,2,5}` and we want to expand it to be of length 6 and end with 3. We first make it to be `{3->4,4->5,1,2,5->6}`, and then, add 3 to the end of the sequence.\n\n```c++\nclass Solution {\npublic:\n    int numPermsDISequence(string S) {\n        int N = S.length() + 1;\n        int MOD = 1e9 + 7;\n        // dp[i][j] means number of permutation whose length is i and end with at most j.\n        int dp[202][202] = {};\n        dp[1][1] = 1;\n        for (int i = 2; i <= N; ++i) {\n            // length is i\n            for (int j = 1; j <= i; ++j) {\n                // end with j\n                if (S[i - 2] == \'D\') {\n                    // decrease to j\n                    dp[i][j] = (dp[i][j-1] + (dp[i-1][i-1] - dp[i-1][j-1]) % MOD) % MOD;\n                } else {\n                    // increase to j\n                    dp[i][j] = (dp[i][j-1] + (dp[i-1][j-1] - dp[i-1][0]) % MOD) % MOD;\n                }\n            }\n        }\n        return (dp[N][N] + MOD) % MOD;\n    }\n};\n```
[]