**Top-down with Memo:**\n\nDefinition: `helper(String s, Map 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 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

Valid Permutations for DI Sequence

Problem Description

Problem Description

Answer Panel