Backtracking to DP Java Solution
Idea\nWe will try all possibilities for all positions and backtracking when we can\'t go further. seen maintains the visited numbers in per recursion tree branc
**Idea**\nWe will try all possibilities for all positions and backtracking when we can\'t go further. `seen` maintains the visited numbers in per recursion tree branch.\n\n**Solution1** **TLE**\n```\nclass Solution {\n    int[] seen = null;\n    public int numPermsDISequence(String s) {\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 += numPerms(s, 0, i);\n            seen[i] = 0;\n        }\n        return count;\n    }\n    private int numPerms(String s, int j, int p){\n        if(j == s.length())\n            return 1;\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 += numPerms(s, j+1, i);\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 += numPerms(s, j+1, i);\n                seen[i] = 0;\n            }\n        }\n        return count;\n    }\n}\n```\n**Solution2** DP Memo for overlapping subproblems. `dp[j][p]` indicates number of permutations till `j`th char in `s` and for permutations ending with number `p` (`p` stands for parent in my recursion, since we are exploring the subtree rooted at `p` in the recursion call).\n```\nclass Solution {\n    private static final int DIV = 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 % DIV + numPerms(s, 0, i) % DIV;\n            seen[i] = 0;\n        }\n        return count % DIV;\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 % DIV + numPerms(s, j+1, i)  % DIV;\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 % DIV + numPerms(s, j+1, i) % DIV;\n                seen[i] = 0;\n            }\n        }\n        dp[j][p] = count % DIV;\n        return dp[j][p];\n    }\n}\n```
[]