Top-down with Memo -> Bottom-up DP -> N^3 DP -> N^2 DP -> O(N) space
Top-down with Memo:\n\nDefinition: helper(String s, Map<String, Long> map): Answer to s.\n\nIntuition: Insert the largest number into appropriate postion.\n\neg
**Top-down with Memo:**\n\nDefinition: `helper(String s, Map<String, Long> map)`: Answer to `s`.\n\nIntuition: Insert the largest number into appropriate postion.\n\neg. `s=\'IIDD\'`, we can only insert `4` between `I` and `D`. We break the remained numbers `0, 1, 2, 3` into two groups both with the size of 2. We have `C(4, 2)` possible combinations. Then `helper("IIDD") = helper("I") * helper("D") * C(4, 2)`.\n\nTricky: How to calculate `C(n, k) % M`? I referred a method using *Pascal Triangle* from [here](https://www.geeksforgeeks.org/compute-ncr-p-set-1-introduction-and-dynamic-programming-solution/). (This part makes this method ugly and lengthy, anybody has better approaches?)\n\nTime complexity: `O(n^4)` in my implementation, however could improve to `O(n^3)`.\n\nCode:\n\n```\nclass Solution {\n    private int M = (int)1e9 + 7;\n    private int[][] nCkMemo;\n    public int numPermsDISequence(String S) {\n        int n = S.length();\n        nCkMemo = new int[n + 1][n + 1];\n        return (int)helper(S, new HashMap<>());\n    }\n    private long helper(String s, Map<String, Long> map) {\n        if (s.equals("")) {\n            return 1;\n        }\n        if (map.containsKey(s)) {\n            return map.get(s);\n        }\n        long result = 0;\n        int n = s.length();\n        if (s.charAt(0) == \'D\') {\n            result += helper(s.substring(1), map);\n            result %= M;\n        }\n        if (s.charAt(n - 1) == \'I\') {\n            result += helper(s.substring(0, n - 1), map);\n            result %= M;\n        }\n        for (int i = 1; i < n; i++) {\n            if (s.charAt(i - 1) == \'I\' && s.charAt(i) == \'D\') {\n                long left = helper(s.substring(0, i - 1), map);\n                long right = helper(s.substring(i + 1), map);\n                result += (((left * right) % M) * nCk(n, i)) % M;\n                result %= M;\n            }\n        }\n        map.put(s, result);\n        return result;\n    }\n    private int nCk(int n, int k) {\n        if (k == 0 || k == n) {\n            return 1;\n        }\n        if (nCkMemo[n][k] == 0) {\n            nCkMemo[n][k] = (nCk(n - 1, k) + nCk(n - 1, k - 1)) % M;\n        }\n        return nCkMemo[n][k];\n    }\n}\n```\n\n**Bottom-up DP:**\n\nSame idea with the Top-down. `dp[i][j]` represent the answer of `s.substring(i, j)`. Just a Bottom-up implementation:\n\nTime complexity: `O(n^3)`\n\n```\nclass Solution {\n    private int M = (int)1e9 + 7;\n    public int numPermsDISequence(String S) {\n        int n = S.length();\n        long[][] dp = new long[n + 1][n + 1];\n        int[][] nCkMemo = new int[n + 1][n + 1];\n        for (int i = 0; i <= n; i++) {\n            dp[i][i] = 1;\n        }\n        for (int len = 1; len <= n; len++) {\n            for (int i = 0; i <= n - len; i++) {\n                int j = i + len;\n                if (S.charAt(i) == \'D\') {\n                    dp[i][j] += dp[i + 1][j];\n                    dp[i][j] %= M;\n                }\n                for (int k = i + 1; k < j; k++) {\n                    if (S.charAt(k - 1) == \'I\' && S.charAt(k) == \'D\') {\n                        dp[i][j] += (((dp[i][k - 1] * dp[k + 1][j]) % M) * nCk(len, k - i, nCkMemo)) % M;\n                        dp[i][j] %= M;\n                    }\n                }\n                if (S.charAt(j - 1) == \'I\') {\n                    dp[i][j] += dp[i][j - 1];\n                    dp[i][j] %= M;\n                }\n            }\n        }\n        return (int)dp[0][n];\n    }\n    private int nCk(int n, int k, int[][] nCkMemo) {\n        if (k == 0 || k == n) {\n            return 1;\n        }\n        if (nCkMemo[n][k] == 0) {\n            nCkMemo[n][k] = (nCk(n - 1, k, nCkMemo) + nCk(n - 1, k - 1, nCkMemo)) % M;\n        }\n        return nCkMemo[n][k];\n    }\n}\n```\n\n**N^3 DP:**\n\nLet\'s change the definition of `dp` matrix to make the calculation simple: let\'s say `dp[i][j]` represents the number of permutation of number `0, 1, ... , i` which ends with `j`. Also, it represents the answer of  `s.substring(0, i)` which ends with `j`.\nWe will have two conditions: \n\n1. `s.charAt(i - 1) == \'I\'`: In this case, `dp[i][j] = sum(dp[i - 1][0], dp[i - 1][1], ... , dp[i - 1][j - 1])`.\n2. `s.charAt(i - 1) == \'D\'`: In this case, `dp[i][j] = sum(dp[i - 1][j], dp[i - 1][j + 1], ... , dp[i - 1][i - 1])`.\n\nImagine each time when appending the `j` to the previous permutations, you have to **add 1 to each number in the previous permutation which is greater than or equals to `j`**. In this way, we keep the orders and counts of previous permutations and cumulate.\n\neg. We already have permutation `(1, 0, 3, 2)`. We are trying to append `2`. Now the `(1, 0, 3, 2)` changes to `(1, 0, 4, 3)` then appended with a `2`. We have `(1, 0, 4, 3, 2)`. Although the values change but the order and count don\'t change.\n\nTime complexity: `O(n^3)`\n\nCode:\n\n```\nclass Solution {\n    public int numPermsDISequence(String S) {\n        int n = S.length(), M = (int)1e9 + 7;\n        int[][] dp = new int[n + 1][n + 1];\n        dp[0][0] = 1;\n        for (int i = 1; i <= n; i++) {\n            for (int j = 0; j <= i; j++) {\n                if (S.charAt(i - 1) == \'D\') {\n                    for (int k = j; k < i; k++) {\n                        dp[i][j] += dp[i - 1][k];\n                        dp[i][j] %= M;\n                    }\n                } else {\n                    for (int k = 0; k < j; k++) {\n                        dp[i][j] += dp[i - 1][k];\n                        dp[i][j] %= M;\n                    }\n                }\n            }\n        }\n        int result = 0;\n        for (int j = 0; j <= n; j++) {\n            result += dp[n][j];\n            result %= M;\n        }\n        return result;\n    }\n}\n```\n\n **N^2 DP:**\n \n Notice that in the previous method, we are actually calculate the **prefix sum** and **suffix sum**  in the two conditions:\n \n1. `s.charAt(i - 1) == \'I\'`: In this case, `dp[i][j] = sum[i - 1][j - 1]`.\n2. `s.charAt(i - 1) == \'D\'`: In this case, `dp[i][j] = sum[i - 1][i - 1] - sum[i - 1][j - 1]`.\n\nWe can define `dp[i][j]` as `sum(dp[i][0], dp[i][1], ... dp[i][j])` which is `sum[i][j]`.\n\nTime complexity: `O(n^2)`\n\nCode:\n\n```\nclass Solution {\n    public int numPermsDISequence(String S) {\n        int n = S.length(), M = (int)1e9 + 7;\n        int[][] dp = new int[n + 1][n + 1];\n        Arrays.fill(dp[0], 1);\n        for (int i = 1; i <= n; i++) {\n            for (int j = 0; j <= i; j++) {\n                dp[i][j] = j == 0 ? 0 : dp[i][j - 1];\n                if (S.charAt(i - 1) == \'D\') {\n                    dp[i][j] += (dp[i - 1][i - 1] - (j == 0 ? 0 : dp[i - 1][j - 1])) % M;\n                    if (dp[i][j] < 0) {\n                        dp[i][j] += M;\n                    }\n                } else {\n                    dp[i][j] += j == 0 ? 0 : dp[i - 1][j - 1];\n                }\n                dp[i][j] %= M;\n            }\n        }\n        return dp[n][n];\n    }\n}\n```\n\n**O(N) space:**\n\nPrevious solution could be optimized to `O(n)` space.\n\nTime complexity: `O(n^2)`. Space complexity: `O(n)`.\n\n```\nclass Solution {\n    public int numPermsDISequence(String S) {\n        int n = S.length(), M = (int)1e9 + 7;\n        int[] dp = new int[n + 1];\n        Arrays.fill(dp, 1);\n        for (int i = 1; i <= n; i++) {\n            int[] temp = new int[n + 1];\n            for (int j = 0; j <= i; j++) {\n                temp[j] = j == 0 ? 0 : temp[j - 1];\n                if (S.charAt(i - 1) == \'D\') {\n                    temp[j] += (dp[i - 1] - (j == 0 ? 0 : dp[j - 1])) % M;\n                    if (temp[j] < 0) {\n                        temp[j] += M;\n                    }\n                } else {\n                    temp[j] += j == 0 ? 0 : dp[j - 1];\n                }\n                temp[j] %= M;\n            }\n            dp = temp;\n        }\n        return dp[n];\n    }\n}\n```\n
[]