Compiling both O(n^2) approaches.
The first approach is based on this post by lee215.\n\nIn both the cases we are avoiding looping through the values already looped through by the previous eleme
The first approach is based on [this](https://leetcode.com/problems/valid-permutations-for-di-sequence/discuss/168278/C%2B%2BJavaPython-DP-Solution-O(N2)) post by lee215.\n\nIn both the cases we are avoiding looping through the values already looped through by the previous element by just using the previous values to make it O(n^2) instead of O(n^3).\n```\n// Runtime: 4ms\nvoid firstApproach(string& s, int n, vvi&dp) {\n        for (int i =0;i<=n;i++) dp[0][i] = 1;\n        for (int i = 1;i<=n;i++) {\n            if (s[i-1] == \'I\') {\n                dp[i][0] = dp[i-1][0];\n                for (int j=1;j<=n-i;j++) {\n                    dp[i][j] = (dp[i][j-1] + dp[i-1][j])%mod; // summing dp[i-1][0..j]\n                }\n            } else {\n                dp[i][n-i] = dp[i-1][n-i+1];\n                for (int j=n-i-1;j>=0;j--) {\n                    dp[i][j] = (dp[i][j+1] + dp[i-1][j+1])%mod; // summing dp[i-1][j+1...n-i+1]\n                }\n            }\n        }\n    }\n```\n\n\nThe second approach is based on the intuitions by wxd_sjtu [here](https://leetcode.com/problems/valid-permutations-for-di-sequence/discuss/196939/Easy-to-understand-solution-with-detailed-explanation), another great explanation by ariawynn [here](https://leetcode.com/problems/valid-permutations-for-di-sequence/discuss/186571/Python-O(N3)O(N2)-time-O(N)-space-DP-solution-with-clear-explanation-(no-%22relative-rank%22-stuff)).\nA great visualisation for this approach is also provided by quadpixels [here](https://leetcode.com/problems/valid-permutations-for-di-sequence/discuss/169126/Visualization-Key-to-the-DP-solution:-imagine-cutting-a-piece-of-paper-and-separating-the-halves)\n\n```\n// Runtime: 4ms\nvoid secondApproach(string& s, int n, vvi&dp) {\n       for (int i=0;i<=n;i++) dp[0][i] = 1;\n       for (int i = 1;i<=n;i++) {\n           if (s[i-1] == \'I\') {\n              dp[i][1] = dp[i-1][0];\n               for (int j = 2;j<=i;j++) {\n                   dp[i][j] = (dp[i][j-1] + dp[i-1][j-1])%mod; // summing dp[i-1][0...j-1]\n               } \n           } else {\n               dp[i][i-1] = dp[i-1][i-1];\n               for (int j = i-2;j>=0;j--) {\n                   dp[i][j] = (dp[i][j+1] + dp[i-1][j])%mod; // summing dp[i-1][j...i-1]\n               }\n           }\n       }\n   }\n```\n\nBoilerplate:\n```\ntypedef vector<int> vi;\ntypedef vector<vi> vvi;\nint mod = 1e9+7;\nint numPermsDISequence(string& s) {\n\tint n = s.size();\n\tvvi dp = vvi(n+1, vi(n+1,0));\n\tfirstApproach(s, n, dp);\n\t//secondApproach(s, n, dp);\n\tint ans =0;\n\tfor (int i: dp[n]) ans = (ans + i)%mod;\n\treturn ans;\n}\n```\n\nJust a compilation, kudos to the original posters.\n
[]