Java- Bottom Up solution- DP
Let\'s define our dp first:\ndp[i][j]=permutations with lenght i with last digit j. The trick is that when you are iterating from i=1 to i=n, you select differe
Let\'s define our dp first:\ndp[i][j]=permutations with lenght i with last digit j. The trick is that when you are iterating from i=1 to i=n, you select different j from 0 to i. Then, for each one of those j, you need to sum the relevant DPs. If S.charAt(i-1)=\'I\', then the prev digit should have been less than the current. So, we use the left half (0,j-1). If it is \'D\', then the prev digit should have been greater than the current one. So, we use (j,i-1). At the end, we sum up the last row dp[n][...] which means all the permuations with length n ending in different digits. Since the result might be big, be careful of the required mods.\n```\n   public int numPermsDISequence(String S) {\n        int mod = 1_000_000_007;\n        int n = S.length();\n        long[][] dp = new long[n + 1][n + 1];\n        dp[0][0] = 1;\n        for (int i = 1; i <= n; i++) { // We start from 1 to\n            char c = S.charAt(i - 1);\n            for (int j = 0; j <= i; j++) { // curr: dp[i][...] prev dp[i-1][...]\n                long sum = 0;\n                if (c == \'I\') { // Increasing- the prev digit was less than the current->use prev(0,j-1)\n                    for (int k = 0; k <= j - 1; k++) sum = (sum + dp[i - 1][k]) % mod;\n                } else { // c==\'D\'- Decreasing- the prev digit was greater than the current->use prev(j,i-1)\n                    for (int k = j; k <= i - 1; k++) sum = (sum + dp[i - 1][k]) % mod;\n                }\n                dp[i][j] = sum;\n            }\n        }\n        Long res = 0L; // Sum the last row- dp[n][...]\n        for (int i = 0; i <= n; i++) res = (res + dp[n][i]) % mod;\n        res = res % mod;\n        return res.intValue();\n    }\n```
[]