C++ O(n^2) solution with only one 1D array. Extremely intuitive detailed thought process
\nclass Solution {\npublic:\n    int numPermsDISequence(string S) {\n        int MOD = 1e9 + 7;\n        deque<int> memo;\n        memo.push_back(1);\n        f
```\nclass Solution {\npublic:\n    int numPermsDISequence(string S) {\n        int MOD = 1e9 + 7;\n        deque<int> memo;\n        memo.push_back(1);\n        for (int i = 0; i < S.size(); i++) {\n            if (S[i] == \'D\') {\n                memo.push_back(0);\n                for (int j = i; j >= 0; j--) {\n                    memo[j] = (memo[j] + memo[j + 1]) % MOD;\n                }\n            } else {\n                assert(S[i] == \'I\');\n                memo.push_front(0);\n                for (int j = 1; j <= i + 1; j++) {\n                    memo[j] = (memo[j] + memo[j - 1]) % MOD;\n                }\n            }\n        }\n        int sum = 0;\n        for (int num: memo) {\n            sum = (sum + num) % MOD;\n        }\n        return sum;\n    }\n};\n```\n\nHow you derives the algorithm? Details below.\n\n# 1. Determine the parameters for DP\nLet\'s say you have already computed numPermsDISequence(3), can you compute numPermsDISequence(4)?\nWe examine a sequence in numPermsDISequence(3), denoted by [ o o o ]. Imagine there are three pointers pointing to each of the token here. So we want to insert an item into the sequence. Let\'s say S[4] = "D", how many ways can we insert the last item?\nObviously, this depend on where the last pointer is pointing to. Let\'s use bold token here to denote the item that the last of the  3 pointers points to, and "I" to denote how you insert the 4th item.\n[ **o** o o ] -> [ I  **o** o o ]       1 way\n[o **o** o ] -> [ I  o **o** o ]  [ o I **o** o ]       2 ways\nso on so forth.\nObviously, the number of ways you can insert the 4th token is dependent on where the 3rd pointer points to. So we need another parameter for DP purpose, which is the index of the last element in the array.\n\n# 2. Derive recursive formula\nNow we have to start from scrach by redefining the function with an additional parameter we just described. Let\'s say we have numPermsDISequence(3, *j*) for *j* in 0~2, which returns the ways of constructing length=3 sequence whose last element is *j*. For simplicity, Let F(*j*)=numPermsDISequence(3, *j*) and F\'(*j*)=numPermsDISequence(4, *j*). How do we compute F\'(*j*)? Again, let\'s assume S[4] = "D".\n\nF\'(0) will produces a sequence of [ I o o o ]. In order for that to happen, the bolden o can be any of the tokens after I. So:\n\n[ I **o** o o ]  [ I o **o** o ]  [ I o o  **o** ]\nF\'(0) = F(0) + F(1) + F(2)\n\nSimilarly, F\'(1) = F(1) + F(2), F\'(2) = F(2), F(3) = 0. Note that F(3) = 0 because there is no way you can produce [ o o o I ] no matter what.\nLet n = 4. You have F\'(j) = sum(F(k)) for k in j~n. To optimize sum computation, we simply compute from F\'(n) to F\'(0), because F\'(k - 1) = sum( j= k-1 to n) = sum( j = k to n ) + F(k - 1) = F\'(k) + F(k - 1)\nIf we already have an array that maintains [ F(0), F(1), F(2) ], for the decreasing case, we only need to append a "0" to the **end of the array**, and then recompute F(2) ~ F(0) from **right to left**.\n[ F(0), F(1), F(2), **F\'(3) = 0** ]\n[ F(0), F(1), **F\'(3) + F(2)**, 0 ]\n[ F(0), **F\'(2) + F(1)**, F\'(3) + F(2), 0 ]\n[ **F\'(1) + F(0)**, F\'(2) + F(1), F\'(3) + F(2), 0 ]\n\nWhen S[4] = "I". We simply mirror everything. We will push a 0 in the **start of the array** and then update sums from **left to right**.\n\nWe need a data structure to insert/remove an item at the beginning/end of array in O(1) time, and random access in O(1) time. Dynamic array will satisfy this requirement, which is deque in c++.\n\n# 3. Compute the result\n\nAt the end of the algorithm, numPermsDISequence(4) is simply ways of constructing arrays that the last element end in either 0, 1, 2 or 3. So result(4) = F\'(0) + F\'(1) + F\'(2) + F\'(3). We can use std::accumulate but due to the MOD requirement we have to compute it manually:(
[]