DP O(N^2), Space O(N), With intuitive walkthrough about how to derive it.
Knowing that we only have to figure out how many permutaitons there are, I stopped thinking about index orders, and instead thought about paths.\n\nConceptually
Knowing that we only have to figure out how many permutaitons there are, I stopped thinking about index orders, and instead thought about paths.\n\nConceptually, with D alone there\'s only one path.\n\n```\n *   \n  \\\n   * (ending)\n ```\n \n If we do DI, then the up path can end either between the existing two nodes, or at the top:\n\n```\n0:      * (ending)\n1: *   /\n    \\ /\n2:   *\n\n0: *\n1:  \\   *(ending)\n     \\ /\n2:    *\n```\n\nThe way I began to represent this is the number of paths that END at a given index.\nD: [0, 1]\nDI: [1, 1, 0]\n\nNow, for DID, we should think about continuing the path that ends at index 0 and 1. Since it will have to go down from there, we\'ll add an index and consider the number of places the current paths can go. When there are more than just 1 paths ending at an index, we\'ll need to preserve the increasing possibilities, so I\'m using variables instead of 1 to show how it should work.\n\n```\n0: x |\n1: y |\n2: z |\n3:   |  (add an index)\n\n// add x to all of the indices below it.\n// add y to all of the indices below it.\n// etc. for each index i from 1..n\n// x = 1, y = 1, z = 0\n0: x |\n1: y | x\n2: z | x y\n3:   | x y z\n\n0: 1 |     -> 0\n1: 1 | 1   -> 1\n2: 0 | 1 1 -> 2\n3:   | 1 1 -> 2\n```\n\nSo DID = [0, 1, 2, 2] (The sum of these = 5)\n\nNow lets take it one step further for each direction to watch how it evolves:\n\n```\nDIDD:\n0: 0 |       -> 0\n1: 1 |       -> 0\n2: 2 | 1     -> 1\n3: 2 | 1 2   -> 3\n4:   | 1 2 2 -> 5\n\nDIDI:\n0: 0 | 2 2 1 | 5\n1: 1 | 2 2 1 | 5\n2: 2 | 2 2   | 4\n3: 2 | 2     | 2\n4: 0 |       | 0\n```\n\nFor increasing the end paths, we have to first imagine shifting all of the indices up (down visually in my ascii art) by one and inserting a new index at 0 => [0 0 1 2 2]. Then accumulating each index to the indices before it. However, we don\'t actually have shift all the data, we can just modify where we read the array from. That\'s why it\'s depicted above as adding the number of ending paths to all of the rows ABOVE OR EQUAL to that index.\n\nNow, at this point, we can look for patterns.\nOne thing I spotted was this:\n```\n0: 0 | 2 2 1 | 5\n1: 1 | 2 2 1 | 5\n2: 2 | 2 2   | 4\n3: 2 | 2     | 2\n4: 0 |       | 0\n-------------------\n       2*4 +\n\t     2*3 +\n\t\t   1*2 +\n\t\t     0*1\n```\nWhich, does give us the answer, but alas isn\'t that useful for determining the next incremental step.\nSo instead looking at each row rather than each column, we can see that "2 2 1" from the previous array is present, at index 0 and 1.\nAnd it\'s essentially a running sum from back to front.\n\nSo now we can translate that into an algorithm to compute each index:\nSo, for the case of "I":\n\nassuming we index into the string with k, S[k] == "I":\nn = k+1\n\n\t// sum from n-1 to 0\n\t// writing from n-1 to 0\n\tdp[n] = 0;\n\tfor (int i = n-1; i >= 0; i--) {\n\t\tdp[i] = (dp[i+1] + dp[i]) % m;\n\t}\n\nNow lets look at D again:\n\n    DIDD:\n\t0: 0 |       -> 0\n\t1: 1 |       -> 0\n\t2: 2 | 1     -> 1\n\t3: 2 | 2 1   -> 3\n\t4:   | 2 2 1 -> 5\n\nIndex 4 shows [2 2 1], and index 3 shows [2 1], so spotting the pattern, just like in the increasing case, we can accumulate the values from the previous step and store them, but this time we need to iterate through the array in the forwards direction when accumulating.\n                \n\t// sum from 0 to n-1\n\t// writing from 1 to n\n\t//sum = dp[0];\n\tint saved  = dp[0];\n\tdp[0] = 0;\n\tfor (int i = 1; i <= n; i++) {\n\t\tint t = dp[i];\n\t\tdp[i] = (dp[i-1] + saved) % m;\n\t\tsaved = t;\n\t}\n\nI\'m having to use some temporary values so I can modify the same array, since we need to iterate through it forward and shift it at the same time.\n\nHere\'s the full solution:\n\n    int numPermsDISequence(string s) {\n        int m = 1000000007;\n        // make the buffer:\n        int dp[s.size()+1];\n        dp[0] = 1;\n        \n        int sum = 0;\n        for (int k = 0; k < s.size(); k++) {\n            int n = k+1;\n            if (s[k] == \'D\') {\n                // sum from 0 to n-1\n                // writing to 1 to n\n                //sum = dp[0];\n                int saved  = dp[0];\n                dp[0] = 0;\n                for (int i = 1; i <= n; i++) {\n                    int t = dp[i];\n                    dp[i] = (dp[i-1] + saved) % m;\n                    saved = t;\n                }\n            } else {\n                // sum from n-1 to 0\n                // writing from n-1 to 0\n                dp[n] = 0;\n                for (int i = n-1; i >= 0; i--) {\n                    dp[i] = (dp[i+1] + dp[i]) % m;\n                }\n            }\n        }\n        sum = 0;\n        for (int i = 0; i <= s.size(); i++) {\n            sum = (sum + dp[i]) % m;\n        }\n        return sum;\n    }
[]