Java DFS with memo
\n\nclass Solution {\n    private static int MOD = 1000000007;\n    public int numPermsDISequence(String S) {\n        int res = 0;\n        Integer[][] dp = ne
\n```\nclass Solution {\n    private static int MOD = 1000000007;\n    public int numPermsDISequence(String S) {\n        int res = 0;\n        Integer[][] dp = new Integer[S.length() + 1][S.length() + 1];\n        \n        for (int i = 0; i <= S.length(); i++) {\n            res += dfs(i, S.length() - i, dp, S, 0);\n            res = res % MOD;\n        }\n        return res;\n    }\n    \n    private int dfs(int higher, int lower, Integer[][] dp, String S, int index) {\n        if (index == S.length()) {\n            return 1;\n        }\n        int d = S.charAt(index) == \'D\' ? 1 : 0;\n        if (dp[higher][lower] != null) {\n            return dp[higher][lower];\n        }\n        int count = 0;\n        if (d == 1) {\n            if (lower > 0) {\n                for (int i = 0; i < lower; i++) {\n                    count += dfs(higher + i, lower - (i + 1), dp, S, index + 1);\n                    count = count % MOD;\n                }\n            }\n        } else {\n            if (higher > 0) {\n                for (int i = 0; i < higher; i++) {\n                    count += dfs(higher - (i + 1), lower + i, dp, S, index + 1);\n                    count = count % MOD;\n                }\n            }\n        }\n        dp[higher][lower] = count;\n        return count;\n    }\n}\n```
[]