JAVA Solution
class Solution {\n    private static final int mod = 1000000007;\n    int[] seen = null;\n    Integer[][] dp = null;\n    public int numPermsDISequence(String s
class Solution {\n    private static final int mod = 1000000007;\n    int[] seen = null;\n    Integer[][] dp = null;\n    public int numPermsDISequence(String s) {\n        dp = new Integer[s.length()][s.length()+1];\n        seen = new int[s.length()+1];\n        int count = 0;\n        for(int i=0; i <= s.length(); i++) {\n            seen[i] = 1;\n        \tcount = count % mod + numPerms(s, 0, i) % mod;\n            seen[i] = 0;\n        }\n        return count % mod;\n    }\n    private int numPerms(String s, int j, int p){\n        if(j == s.length())\n            return 1;\n        if(dp[j][p] != null) return dp[j][p];\n        char ch = s.charAt(j);\n        int count = 0;\n        if(ch == \'D\'){\n            for(int i=p-1; i >= 0; i--){\n                if(seen[i] == 1)\n                    continue;\n                seen[i] = 1;\n                count = count % mod + numPerms(s, j+1, i)  % mod;\n                seen[i] = 0;\n            }\n        }else{\n            for(int i=p+1; i <= s.length(); i++){\n                if(seen[i] == 1)\n                    continue;\n                seen[i] = 1;\n                count = count % mod + numPerms(s, j+1, i) % mod;\n                seen[i] = 0;\n            }\n        }\n        dp[j][p] = count % mod;\n        return dp[j][p];\n    }\n}
['Dynamic Programming', 'Memoization', 'Java']