java easy memoization after recursion | DP
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    int mod = 1000000007;\n    public int numPermsDISequence(String s) {\n        int n=s.length();\n        int cnt=0;\n        boolean check[]=new boolean[n+1];\n         Integer dp[][]=new Integer[n+1][n+1];\n        for(int i=0;i<=n;i++){\n            check[i]=true;\n            cnt+=fun(n-1,n,s.toCharArray(),i ,check, dp); cnt%=mod;\n            check[i]=false;\n        }\n        return cnt%mod;\n    }\n    private int fun(int i, int n, char str[], int next,boolean check[], Integer dp[][]){\n         if(i < 0)return 1;\n\n         if(dp[i][next] != null)return dp[i][next]%mod;\n         \n         int count=0;\n         for(int j=0;j<=n;j++){\n             if(check[j])continue;\n             if(str[i] == \'D\'){\n                 if(j > next){\n                    check[j]=true;\n                    count+=fun(i-1,n,str,j , check , dp); count%=mod;\n                    check[j]=false;\n                 }\n             }else{\n                 if(j < next){\n                    check[j]=true;\n                    count+=fun(i-1,n,str,j, check , dp); count%=mod;\n                    check[j]=false;\n                 }\n             }\n         }\n\n        return dp[i][next] = count%mod;\n    }\n}\n```
['Dynamic Programming', 'Memoization', 'Java']